/*
 * NFA 工具。
 * 此文件由 regcomp.c 包含。
 *
 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 *
 * 本软件的开发部分由 Cray Research Inc.、UUNET Communications Services Inc.、Sun Microsystems Inc. 和 Scriptics Corporation 资助， 他们都不对结果负责。作者对他们表示感谢。
 *
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 *
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * src/backend/regex/regc_nfa.c
 *
 *
 * 一两件技术上应该在这里的事情实际上在 color.c 中，感谢颜色链中的一些乱伦关系。
 */

#define NISERR()	VISERR(nfa->v)
#define NERR(e)		VERR(nfa->v, (e))


/*
 * newnfa - 设置一个NFA
 */
static struct nfa *				/* NFA，或NULL */
newnfa(struct vars *v,
	   struct colormap *cm,
	   struct nfa *fc_parent)		/* 如果是主要NFA，则为NULL */
{
	struct nfa *fc_nfa;

	fc_nfa = (struct nfa *) MALLOC(sizeof(struct nfa));
	if (fc_nfa == NULL)
	{
		ERR(REG_ESPACE);
		return NULL;
	}

	/* 使NFA最小有效，以便freenfa()可以正常工作 */
	fc_nfa->states = NULL;
	fc_nfa->slast = NULL;
	fc_nfa->freestates = NULL;
	fc_nfa->freearcs = NULL;
	fc_nfa->lastsb = NULL;
	fc_nfa->lastab = NULL;
	fc_nfa->lastsbused = 0;
	fc_nfa->lastabused = 0;
	fc_nfa->nstates = 0;
	fc_nfa->cm = cm;
	fc_nfa->v = v;
	fc_nfa->bos[0] = fc_nfa->bos[1] = COLORLESS;
	fc_nfa->eos[0] = fc_nfa->eos[1] = COLORLESS;
	fc_nfa->flags = 0;
	fc_nfa->minmatchall = fc_nfa->maxmatchall = -1;
	fc_nfa->parent = fc_parent;		/* 在newfstate之前，使父节点有效。 */

	/* 创建所需的基础设施 */
	fc_nfa->post = newfstate(fc_nfa, '@');	/* number 0 */
	fc_nfa->pre = newfstate(fc_nfa, '>'); /* number 1 */
	fc_nfa->init = newstate(fc_nfa);	/* 可能会稍后无效 */
	fc_nfa->final = newstate(fc_nfa);
	if (ISERR())
	{
		freenfa(fc_nfa);
		return NULL;
	}
	rainbow(fc_nfa, fc_nfa->cm, PLAIN, COLORLESS, fc_nfa->pre, fc_nfa->init);
	newarc(fc_nfa, '^', 1, fc_nfa->pre, fc_nfa->init);
	newarc(fc_nfa, '^', 0, fc_nfa->pre, fc_nfa->init);
	rainbow(fc_nfa, fc_nfa->cm, PLAIN, COLORLESS, fc_nfa->final, fc_nfa->post);
	newarc(fc_nfa, '$', 1, fc_nfa->final, fc_nfa->post);
	newarc(fc_nfa, '$', 0, fc_nfa->final, fc_nfa->post);

	if (ISERR())
	{
		freenfa(fc_nfa);
		return NULL;
	}
	return fc_nfa;
}

/*
 * freenfa - 释放整个NFA
 */
static void freenfa(struct nfa *fc_nfa)
{
	struct statebatch *fc_sb;
	struct statebatch *fc_sbnext;
	struct arcbatch *fc_ab;
	struct arcbatch *fc_abnext;

	for (fc_sb = fc_nfa->lastsb; fc_sb != NULL; fc_sb = fc_sbnext)
	{
		fc_sbnext = fc_sb->next;
		fc_nfa->v->spaceused -= STATEBATCHSIZE(fc_sb->nstates);
		FREE(fc_sb);
	}
	fc_nfa->lastsb = NULL;
	for (fc_ab = fc_nfa->lastab; fc_ab != NULL; fc_ab = fc_abnext)
	{
		fc_abnext = fc_ab->next;
		fc_nfa->v->spaceused -= ARCBATCHSIZE(fc_ab->narcs);
		FREE(fc_ab);
	}
	fc_nfa->lastab = NULL;

	fc_nfa->nstates = -1;
	FREE(fc_nfa);
}

/*
 * newstate - 分配一个NFA状态，标志值为零
 */
static struct state *			/* 出错时为NULL */
newstate(struct nfa *nfa)
{
	struct state *fc_s;

	/*
	 * 这是在正则表达式编译期间检查操作取消的便捷位置，
	 * 因为没有代码路径会在不创建新状态或连接的情况下走得太长。
	 */
	if (CANCEL_REQUESTED(nfa->v->re))
	{
		NERR(REG_CANCEL);
		return NULL;
	}

	/* 首先，回收闲置列表中的任何内容 */
	if (nfa->freestates != NULL)
	{
		fc_s = nfa->freestates;
		nfa->freestates = fc_s->next;
	}
	/* 否则，最后的状态批次中还有什么吗？ */
	else if (nfa->lastsb != NULL && nfa->lastsbused < nfa->lastsb->nstates)
	{
		fc_s = &nfa->lastsb->s[nfa->lastsbused++];
	}
	/* 否则，需要分配一个新的状态批次 */
	else
	{
		struct statebatch *fc_newSb;
		size_t		fc_nstates;

		if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE)
		{
			NERR(REG_ETOOBIG);
			return NULL;
		}
		fc_nstates = (nfa->lastsb != NULL) ? nfa->lastsb->nstates * 2 : FIRSTSBSIZE;
		if (fc_nstates > MAXSBSIZE)
			fc_nstates = MAXSBSIZE;
		fc_newSb = (struct statebatch *) MALLOC(STATEBATCHSIZE(fc_nstates));
		if (fc_newSb == NULL)
		{
			NERR(REG_ESPACE);
			return NULL;
		}
		nfa->v->spaceused += STATEBATCHSIZE(fc_nstates);
		fc_newSb->nstates = fc_nstates;
		fc_newSb->next = nfa->lastsb;
		nfa->lastsb = fc_newSb;
		nfa->lastsbused = 1;
		fc_s = &fc_newSb->s[0];
	}

	assert(nfa->nstates >= 0);
	fc_s->no = nfa->nstates++;
	fc_s->flag = 0;
	if (nfa->states == NULL)
		nfa->states = fc_s;
	fc_s->nins = 0;
	fc_s->ins = NULL;
	fc_s->nouts = 0;
	fc_s->outs = NULL;
	fc_s->tmp = NULL;
	fc_s->next = NULL;
	if (nfa->slast != NULL)
	{
		assert(nfa->slast->next == NULL);
		nfa->slast->next = fc_s;
	}
	fc_s->prev = nfa->slast;
	nfa->slast = fc_s;
	return fc_s;
}

/*
 * newfstate - 以指定的标志值分配一个NFA状态
 */
static struct state *			/* 出错时为NULL */
newfstate(struct nfa *fc_nfa, int fc_flag)
{
	struct state *s;

	s = newstate(fc_nfa);
	if (s != NULL)
		s->flag = (char) fc_flag;
	return s;
}

/*
 * dropstate - 删除状态的入弧和出弧并释放它
 */
static void dropstate(struct nfa *fc_nfa,
		  struct state *fc_s)
{
	struct arc *fc_a;

	while ((fc_a = fc_s->ins) != NULL)
		freearc(fc_nfa, fc_a);
	while ((fc_a = fc_s->outs) != NULL)
		freearc(fc_nfa, fc_a);
	freestate(fc_nfa, fc_s);
}

/*
 * freestate - 释放一个没有入弧或出弧的状态
 */
static void freestate(struct nfa *fc_nfa,
		  struct state *fc_s)
{
	assert(fc_s != NULL);
	assert(fc_s->nins == 0 && fc_s->nouts == 0);

	fc_s->no = FREESTATE;
	fc_s->flag = 0;
	if (fc_s->next != NULL)
		fc_s->next->prev = fc_s->prev;
	else
	{
		assert(fc_s == fc_nfa->slast);
		fc_nfa->slast = fc_s->prev;
	}
	if (fc_s->prev != NULL)
		fc_s->prev->next = fc_s->next;
	else
	{
		assert(fc_s == fc_nfa->states);
		fc_nfa->states = fc_s->next;
	}
	fc_s->prev = NULL;
	fc_s->next = fc_nfa->freestates;	/* 不要删除它，将其放入空闲列表 */
	fc_nfa->freestates = fc_s;
}

/*
 * newarc - 在NFA中设置新的弧
 *
 * 此函数确保不会创建重复的弧。
 * 通常我们不希望有重复。
 *
 * 然而：原则上，RAINBOW弧与任何普通弧是冗余的
 * （除非该弧用于伪色）。但是我们并不尝试识别
 * 那种冗余，无论是在这里还是在像moveins()这样的相关操作中。
 * 伪色的考虑使这比看起来更加复杂且不值得尝试。
 */
static void newarc(struct nfa *nfa,
	   int fc_t,
	   color fc_co,
	   struct state *fc_from,
	   struct state *fc_to)
{
	struct arc *fc_a;

	assert(fc_from != NULL && fc_to != NULL);

	/*
	 * 这是在正则表达式编译期间检查操作取消的便捷位置，
	 * 因为没有代码路径会在不创建新状态或连接的情况下走得太长。
	 */
	if (CANCEL_REQUESTED(nfa->v->re))
	{
		NERR(REG_CANCEL);
		return;
	}

	/* 检查重复弧，使用较短的链条 */
	if (fc_from->nouts <= fc_to->nins)
	{
		for (fc_a = fc_from->outs; fc_a != NULL; fc_a = fc_a->outchain)
			if (fc_a->to == fc_to && fc_a->co == fc_co && fc_a->type == fc_t)
				return;
	}
	else
	{
		for (fc_a = fc_to->ins; fc_a != NULL; fc_a = fc_a->inchain)
			if (fc_a->from == fc_from && fc_a->co == fc_co && fc_a->type == fc_t)
				return;
	}

	/* 没有重复，所以创建弧 */
	createarc(nfa, fc_t, fc_co, fc_from, fc_to);
}

/*
 * createarc - 在NFA中创建新的弧
 *
 * 此函数必须*仅在验证不存在
 * 相同的弧（相同类型/颜色/来自/到）后使用。
 */
static void createarc(struct nfa *nfa,
		  int fc_t,
		  color fc_co,
		  struct state *fc_from,
		  struct state *fc_to)
{
	struct arc *fc_a;

	fc_a = allocarc(nfa);
	if (NISERR())
		return;
	assert(fc_a != NULL);

	fc_a->type = fc_t;
	fc_a->co = fc_co;
	fc_a->to = fc_to;
	fc_a->from = fc_from;

	/*
	 * 将新弧放在链条的开头，而不是末尾；这在这里
	 * 更简单，freearc()的成本无论如何都是相同的。另见
	 * moveins()及其相关函数中的逻辑，以及fixempties()。
	 */
	fc_a->inchain = fc_to->ins;
	fc_a->inchainRev = NULL;
	if (fc_to->ins)
		fc_to->ins->inchainRev = fc_a;
	fc_to->ins = fc_a;
	fc_a->outchain = fc_from->outs;
	fc_a->outchainRev = NULL;
	if (fc_from->outs)
		fc_from->outs->outchainRev = fc_a;
	fc_from->outs = fc_a;

	fc_from->nouts++;
	fc_to->nins++;

	if (COLORED(fc_a) && nfa->parent == NULL)
		colorchain(nfa->cm, fc_a);
}

/*
 * allocarc - 在NFA中分配新的弧
 */
static struct arc *				/* NULL表示失败 */
allocarc(struct nfa *nfa)
{
	struct arc *fc_a;

	/* 首先，回收闲置列表中的任何内容 */
	if (nfa->freearcs != NULL)
	{
		fc_a = nfa->freearcs;
		nfa->freearcs = fc_a->freechain;
	}
	/* 否则，最后的arcbatch中还有什么吗？ */
	else if (nfa->lastab != NULL && nfa->lastabused < nfa->lastab->narcs)
	{
		fc_a = &nfa->lastab->a[nfa->lastabused++];
	}
	/* 否则，需要分配新的arcbatch */
	else
	{
		struct arcbatch *fc_newAb;
		size_t		fc_narcs;

		if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE)
		{
			NERR(REG_ETOOBIG);
			return NULL;
		}
		fc_narcs = (nfa->lastab != NULL) ? nfa->lastab->narcs * 2 : FIRSTABSIZE;
		if (fc_narcs > MAXABSIZE)
			fc_narcs = MAXABSIZE;
		fc_newAb = (struct arcbatch *) MALLOC(ARCBATCHSIZE(fc_narcs));
		if (fc_newAb == NULL)
		{
			NERR(REG_ESPACE);
			return NULL;
		}
		nfa->v->spaceused += ARCBATCHSIZE(fc_narcs);
		fc_newAb->narcs = fc_narcs;
		fc_newAb->next = nfa->lastab;
		nfa->lastab = fc_newAb;
		nfa->lastabused = 1;
		fc_a = &fc_newAb->a[0];
	}

	return fc_a;
}

/*
 * freearc - 释放一个弧
 */
static void freearc(struct nfa *fc_nfa,
		struct arc *fc_victim)
{
	struct state *fc_from = fc_victim->from;
	struct state *fc_to = fc_victim->to;
	struct arc *fc_predecessor;

	assert(fc_victim->type != 0);

	/* 如有必要，将其从颜色链中移除 */
	if (COLORED(fc_victim) && fc_nfa->parent == NULL)
		uncolorchain(fc_nfa->cm, fc_victim);

	/* 从源的出链中移除 */
	assert(fc_from != NULL);
	fc_predecessor = fc_victim->outchainRev;
	if (fc_predecessor == NULL)
	{
		assert(fc_from->outs == fc_victim);
		fc_from->outs = fc_victim->outchain;
	}
	else
	{
		assert(fc_predecessor->outchain == fc_victim);
		fc_predecessor->outchain = fc_victim->outchain;
	}
	if (fc_victim->outchain != NULL)
	{
		assert(fc_victim->outchain->outchainRev == fc_victim);
		fc_victim->outchain->outchainRev = fc_predecessor;
	}
	fc_from->nouts--;

	/* 从目标的入链中移除 */
	assert(fc_to != NULL);
	fc_predecessor = fc_victim->inchainRev;
	if (fc_predecessor == NULL)
	{
		assert(fc_to->ins == fc_victim);
		fc_to->ins = fc_victim->inchain;
	}
	else
	{
		assert(fc_predecessor->inchain == fc_victim);
		fc_predecessor->inchain = fc_victim->inchain;
	}
	if (fc_victim->inchain != NULL)
	{
		assert(fc_victim->inchain->inchainRev == fc_victim);
		fc_victim->inchain->inchainRev = fc_predecessor;
	}
	fc_to->nins--;

	/* 清理并放置在NFA的空闲列表中 */
	fc_victim->type = 0;
	fc_victim->from = NULL;		/* 预防措施... */
	fc_victim->to = NULL;
	fc_victim->inchain = NULL;
	fc_victim->inchainRev = NULL;
	fc_victim->outchain = NULL;
	fc_victim->outchainRev = NULL;
	fc_victim->freechain = fc_nfa->freearcs;
	fc_nfa->freearcs = fc_victim;
}

/*
 * changearcsource - 翻转弧以具有不同的来自状态
 *
 * 调用者必须验证不存在预先存在的重复弧。
 */
static void changearcsource(struct arc *fc_a, struct state *fc_newfrom)
{
	struct state *fc_oldfrom = fc_a->from;
	struct arc *fc_predecessor;

	assert(fc_oldfrom != fc_newfrom);

	/* 从旧源的出链中移除 */
	assert(fc_oldfrom != NULL);
	fc_predecessor = fc_a->outchainRev;
	if (fc_predecessor == NULL)
	{
		assert(fc_oldfrom->outs == fc_a);
		fc_oldfrom->outs = fc_a->outchain;
	}
	else
	{
		assert(fc_predecessor->outchain == fc_a);
		fc_predecessor->outchain = fc_a->outchain;
	}
	if (fc_a->outchain != NULL)
	{
		assert(fc_a->outchain->outchainRev == fc_a);
		fc_a->outchain->outchainRev = fc_predecessor;
	}
	fc_oldfrom->nouts--;

	fc_a->from = fc_newfrom;

	/* 将其添加到新源的出链前 */
	fc_a->outchain = fc_newfrom->outs;
	fc_a->outchainRev = NULL;
	if (fc_newfrom->outs)
		fc_newfrom->outs->outchainRev = fc_a;
	fc_newfrom->outs = fc_a;
	fc_newfrom->nouts++;
}

/*
 * changearctarget - 翻转弧以具有不同的到达状态
 *
 * 调用者必须验证不存在预先存在的重复弧。
 */
static void changearctarget(struct arc *fc_a, struct state *fc_newto)
{
	struct state *fc_oldto = fc_a->to;
	struct arc *fc_predecessor;

	assert(fc_oldto != fc_newto);

	/* 从旧目标的入链中移除 */
	assert(fc_oldto != NULL);
	fc_predecessor = fc_a->inchainRev;
	if (fc_predecessor == NULL)
	{
		assert(fc_oldto->ins == fc_a);
		fc_oldto->ins = fc_a->inchain;
	}
	else
	{
		assert(fc_predecessor->inchain == fc_a);
		fc_predecessor->inchain = fc_a->inchain;
	}
	if (fc_a->inchain != NULL)
	{
		assert(fc_a->inchain->inchainRev == fc_a);
		fc_a->inchain->inchainRev = fc_predecessor;
	}
	fc_oldto->nins--;

	fc_a->to = fc_newto;

	/* 将其添加到新目标的入链前 */
	fc_a->inchain = fc_newto->ins;
	fc_a->inchainRev = NULL;
	if (fc_newto->ins)
		fc_newto->ins->inchainRev = fc_a;
	fc_newto->ins = fc_a;
	fc_newto->nins++;
}

/*
 * hasnonemptyout - 状态是否具有非EMPTY出弧？
 */
static int hasnonemptyout(struct state *fc_s)
{
	struct arc *fc_a;

	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		if (fc_a->type != EMPTY)
			return 1;
	}
	return 0;
}

/*
 * findarc - 从给定源找到弧（如果有），具有给定的类型和颜色
 * 如果有多个这样的弧，则结果是随机的。
 */
static struct arc *
findarc(struct state *fc_s,
		int fc_type,
		color fc_co)
{
	struct arc *fc_a;

	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
		if (fc_a->type == fc_type && fc_a->co == fc_co)
			return fc_a;
	return NULL;
}

/*
 * cparc - 在NFA中分配新的弧，复制旧弧的详细信息
 */
static void cparc(struct nfa *fc_nfa,
	  struct arc *fc_oa,
	  struct state *fc_from,
	  struct state *fc_to)
{
	newarc(fc_nfa, fc_oa->type, fc_oa->co, fc_from, fc_to);
}

/*
 * sortins - 按from/color/type对状态的入弧进行排序
 */
static void sortins(struct nfa *nfa,
		struct state *fc_s)
{
	struct arc **fc_sortarray;
	struct arc *fc_a;
	int			fc_n = fc_s->nins;
	int			fc_i;

	if (fc_n <= 1)
		return;					/* 无需操作 */
	/* 创建弧指针数组... */
	fc_sortarray = (struct arc **) MALLOC(fc_n * sizeof(struct arc *));
	if (fc_sortarray == NULL)
	{
		NERR(REG_ESPACE);
		return;
	}
	fc_i = 0;
	for (fc_a = fc_s->ins; fc_a != NULL; fc_a = fc_a->inchain)
		fc_sortarray[fc_i++] = fc_a;
	assert(fc_i == fc_n);
	/* ... 对数组进行排序 */
	qsort(fc_sortarray, fc_n, sizeof(struct arc *), sortins_cmp);
	/* ... 并按顺序重建弧列表 */
	
/* 似乎值得为第一个和最后一个项目特别处理，以简化循环 */
	fc_a = fc_sortarray[0];
	fc_s->ins = fc_a;
	fc_a->inchain = fc_sortarray[1];
	fc_a->inchainRev = NULL;
	for (fc_i = 1; fc_i < fc_n - 1; fc_i++)
	{
		fc_a = fc_sortarray[fc_i];
		fc_a->inchain = fc_sortarray[fc_i + 1];
		fc_a->inchainRev = fc_sortarray[fc_i - 1];
	}
	fc_a = fc_sortarray[fc_i];
	fc_a->inchain = NULL;
	fc_a->inchainRev = fc_sortarray[fc_i - 1];
	FREE(fc_sortarray);
}

static int sortins_cmp(const void *fc_a, const void *fc_b)
{
	const struct arc *fc_aa = *((const struct arc *const *) fc_a);
	const struct arc *fc_bb = *((const struct arc *const *) fc_b);

	/* 我们按最可能不同的顺序检查字段 */
	if (fc_aa->from->no < fc_bb->from->no)
		return -1;
	if (fc_aa->from->no > fc_bb->from->no)
		return 1;
	if (fc_aa->co < fc_bb->co)
		return -1;
	if (fc_aa->co > fc_bb->co)
		return 1;
	if (fc_aa->type < fc_bb->type)
		return -1;
	if (fc_aa->type > fc_bb->type)
		return 1;
	return 0;
}

/*
 * sortouts - 按照到达/颜色/类型对状态的出弧进行排序
 */
static void sortouts(struct nfa *nfa,
		 struct state *fc_s)
{
	struct arc **sortarray;
	struct arc *fc_a;
	int			fc_n = fc_s->nouts;
	int			fc_i;

	if (fc_n <= 1)
		return;					/* 无需操作 */
	/* 创建弧指针数组... */
	sortarray = (struct arc **) MALLOC(fc_n * sizeof(struct arc *));
	if (sortarray == NULL)
	{
		NERR(REG_ESPACE);
		return;
	}
	fc_i = 0;
	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
		sortarray[fc_i++] = fc_a;
	assert(fc_i == fc_n);
	/* ... 对数组进行排序 */
	qsort(sortarray, fc_n, sizeof(struct arc *), sortouts_cmp);
	/* ... 并按顺序重建弧列表 */
	
/* 似乎值得为第一个和最后一个项目特别处理，以简化循环 */
	fc_a = sortarray[0];
	fc_s->outs = fc_a;
	fc_a->outchain = sortarray[1];
	fc_a->outchainRev = NULL;
	for (fc_i = 1; fc_i < fc_n - 1; fc_i++)
	{
		fc_a = sortarray[fc_i];
		fc_a->outchain = sortarray[fc_i + 1];
		fc_a->outchainRev = sortarray[fc_i - 1];
	}
	fc_a = sortarray[fc_i];
	fc_a->outchain = NULL;
	fc_a->outchainRev = sortarray[fc_i - 1];
	FREE(sortarray);
}

static int sortouts_cmp(const void *fc_a, const void *fc_b)
{
	const struct arc *fc_aa = *((const struct arc *const *) fc_a);
	const struct arc *fc_bb = *((const struct arc *const *) fc_b);

	/* 我们按最可能不同的顺序检查字段 */
	if (fc_aa->to->no < fc_bb->to->no)
		return -1;
	if (fc_aa->to->no > fc_bb->to->no)
		return 1;
	if (fc_aa->co < fc_bb->co)
		return -1;
	if (fc_aa->co > fc_bb->co)
		return 1;
	if (fc_aa->type < fc_bb->type)
		return -1;
	if (fc_aa->type > fc_bb->type)
		return 1;
	return 0;
}

/*
 * 关于是否使用逐弧操作或排序/合并的常见决策逻辑。如果源弧很少，
 * 我们无法收回排序目标弧列表的成本，无论它有多大。否则，将逐弧比较的数量
 * 限制在大约1000（这是一个相当任意的选择，但平衡点可能与机器相关）。
 */
#define BULK_ARC_OP_USE_SORT(nsrcarcs, ndestarcs) \
	((nsrcarcs) < 4 ? 0 : ((nsrcarcs) > 32 || (ndestarcs) > 32))

/*
 * moveins - 将一个状态的所有入弧移动到另一个状态
 *
 * 你可能会认为只需更新现有弧就可以做得更好，如果不是出于
 * 重复抑制的需要，你说得对，这使得创建新的弧以利用新的新弧
 * 内置的抑制功能变得更容易。
 *
 * 然而，如果我们要处理大量弧，零售的重复检查会变得太慢。
 * 在这种情况下，我们通过排序和合并弧列表来处理，然后
 * 我们确实可以就地更新弧。
 *
 * 另一方面，这种情况也常常伴随着全新的新状态，其中没有
 * 现有的入弧。在这种情况下，去重是不必要的，因此我们
 * 可以盲目地移动所有弧。
 */
static void moveins(struct nfa *nfa,
		struct state *fc_oldState,
		struct state *fc_newState)
{
	assert(fc_oldState != fc_newState);

	if (fc_newState->nins == 0)
	{
		/* 无需去重 */
		struct arc *fc_a;

		while ((fc_a = fc_oldState->ins) != NULL)
		{
			createarc(nfa, fc_a->type, fc_a->co, fc_a->from, fc_newState);
			freearc(nfa, fc_a);
		}
	}
	else if (!BULK_ARC_OP_USE_SORT(fc_oldState->nins, fc_newState->nins))
	{
		/* 当弧不多时，逐个处理它们 */
		struct arc *fc_a;

		while ((fc_a = fc_oldState->ins) != NULL)
		{
			cparc(nfa, fc_a, fc_a->from, fc_newState);
			freearc(nfa, fc_a);
		}
	}
	else
	{
		/*
		 * 当弧很多时，使用排序合并的方法。注意 changearctarget()
		 * 会将弧放到新状态链的前面，因此不会破坏我们
		 * 在链的排序部分的遍历。
		 */
		struct arc *fc_oa;
		struct arc *fc_na;

		/*
		 * 由于我们在这条代码路径中绕过了 newarc()，我们最好
		 * 包含一个取消检查。
		 */
		if (CANCEL_REQUESTED(nfa->v->re))
		{
			NERR(REG_CANCEL);
			return;
		}

		sortins(nfa, fc_oldState);
		sortins(nfa, fc_newState);
		if (NISERR())
			return;				/* 可能未能排序 */
		fc_oa = fc_oldState->ins;
		fc_na = fc_newState->ins;
		while (fc_oa != NULL && fc_na != NULL)
		{
			struct arc *fc_a = fc_oa;

			switch (sortins_cmp(&fc_oa, &fc_na))
			{
				case -1:
					/* newState 没有匹配的 oa */
					fc_oa = fc_oa->inchain;

					/*
					 * 与其执行 createarc + freearc，不如直接解除链接
					 * 并重新链接现有的弧结构。
					 */
					changearctarget(fc_a, fc_newState);
					break;
				case 0:
					/* 匹配，两个列表都向前推进 */
					fc_oa = fc_oa->inchain;
					fc_na = fc_na->inchain;
					/* ... 并从 oldState 中删除重复弧 */
					freearc(nfa, fc_a);
					break;
				case +1:
					/* 仅推进 na； oa 可能在后面有匹配 */
					fc_na = fc_na->inchain;
					break;
				default:
					assert(NOTREACHED);
			}
		}
		while (fc_oa != NULL)
		{
			/* newState 没有匹配的 oa */
			struct arc *fc_a = fc_oa;

			fc_oa = fc_oa->inchain;
			changearctarget(fc_a, fc_newState);
		}
	}

	assert(fc_oldState->nins == 0);
	assert(fc_oldState->ins == NULL);
}

/*
 * copyins - 将一个状态的弧复制到另一个状态
 *
 * moveins() 的注释同样适用。然而，在当前的使用中，
 * 这 * 仅 * 被调用于全新的目标状态，因此
 * 只会进入“无需去重”的代码路径。我们保持其余部分
 * 用 #ifdef 注释掉，以备将来需要。
 */
static void copyins(struct nfa *nfa,
		struct state *fc_oldState,
		struct state *fc_newState)
{
	assert(fc_oldState != fc_newState);
	assert(fc_newState->nins == 0);	/* 请参见上面的注释 */

	if (fc_newState->nins == 0)
	{
		/* 无需去重 */
		struct arc *fc_a;

		for (fc_a = fc_oldState->ins; fc_a != NULL; fc_a = fc_a->inchain)
			createarc(nfa, fc_a->type, fc_a->co, fc_a->from, fc_newState);
	}
#ifdef NOT_USED					/* 请参见上面的注释 */
	else if (!BULK_ARC_OP_USE_SORT(fc_oldState->nins, fc_newState->nins))
	{
		/* 当弧不多时，逐个处理它们 */
		struct arc *fc_a;

		for (fc_a = fc_oldState->ins; fc_a != NULL; fc_a = fc_a->inchain)
			cparc(nfa, fc_a, fc_a->from, fc_newState);
	}
	else
	{
		/*
		 * 当弧很多时，使用排序合并的方法。注意 createarc()
		 * 会将新弧放到新状态链的前面，因此不会破坏我们
		 * 在链的排序部分的遍历。
		 */
		struct arc *fc_oa;
		struct arc *fc_na;

		/*
		 * 由于我们在这条代码路径中绕过了 newarc()，我们最好
		 * 包含一个取消检查。
		 */
		if (CANCEL_REQUESTED(nfa->v->re))
		{
			NERR(REG_CANCEL);
			return;
		}

		sortins(nfa, fc_oldState);
		sortins(nfa, fc_newState);
		if (NISERR())
			return;				/* 可能未能排序 */
		fc_oa = fc_oldState->ins;
		fc_na = fc_newState->ins;
		while (fc_oa != NULL && fc_na != NULL)
		{
			struct arc *fc_a = fc_oa;

			switch (sortins_cmp(&fc_oa, &fc_na))
			{
				case -1:
					/* newState 没有匹配的 oa */
					fc_oa = fc_oa->inchain;
					createarc(nfa, fc_a->type, fc_a->co, fc_a->from, fc_newState);
					break;
				case 0:
					/* 匹配，两个列表都向前推进 */
					fc_oa = fc_oa->inchain;
					fc_na = fc_na->inchain;
					break;
				case +1:
					/* 仅推进 na； oa 可能在后面有匹配 */
					fc_na = fc_na->inchain;
					break;
				default:
					assert(NOTREACHED);
			}
		}
		while (fc_oa != NULL)
		{
			/* newState 没有匹配的 oa */
			struct arc *fc_a = fc_oa;

			fc_oa = fc_oa->inchain;
			createarc(nfa, fc_a->type, fc_a->co, fc_a->from, fc_newState);
		}
	}
#endif							/* 在较旧的 Perl 上值得怀疑... */
}

/*
 * mergeins - 将一组入弧合并到一个状态
 *
 * 这与 copyins 非常相似，但源弧在数组中列出，
 * 并且不保证唯一。覆盖数组内容是可以的。
 */
static void mergeins(struct nfa *nfa,
		 struct state *fc_s,
		 struct arc **fc_arcarray,
		 int fc_arccount)
{
	struct arc *na;
	int			fc_i;
	int			fc_j;

	if (fc_arccount <= 0)
		return;

	/*
	 * 由于我们在这条代码路径中绕过了 newarc()，我们最好
	 * 包含一个取消检查。
	 */
	if (CANCEL_REQUESTED(nfa->v->re))
	{
		NERR(REG_CANCEL);
		return;
	}

	/* 对已有入弧和提议的新弧进行排序 */
	sortins(nfa, fc_s);
	if (NISERR())
		return;					/* 可能未能排序 */

	qsort(fc_arcarray, fc_arccount, sizeof(struct arc *), sortins_cmp);

	/*
	 * arcarray 很可能包含重复项，因此我们必须消除它们。 
	 * （这可以合并到下一个循环中，但没有必要麻烦。）
	 */
	fc_j = 0;
	for (fc_i = 1; fc_i < fc_arccount; fc_i++)
	{
		switch (sortins_cmp(&fc_arcarray[fc_j], &fc_arcarray[fc_i]))
		{
			case -1:
				/* non-dup */
				fc_arcarray[++fc_j] = fc_arcarray[fc_i];
				break;
			case 0:
				/* dup */
				break;
			default:
				/* 有问题 */
				assert(NOTREACHED);
		}
	}
	fc_arccount = fc_j + 1;

	/*
	 * 现在合并到 s' 的 inchain 中。注意 createarc()
	 * 会将新弧放到 s 的链的前面，因此不会破坏我们遍历
	 * 链的排序部分。
	 */
	fc_i = 0;
	na = fc_s->ins;
	while (fc_i < fc_arccount && na != NULL)
	{
		struct arc *a = fc_arcarray[fc_i];

		switch (sortins_cmp(&a, &na))
		{
			case -1:
				/* s 没有匹配的 a */
				createarc(nfa, a->type, a->co, a->from, fc_s);
				fc_i++;
				break;
			case 0:
				/* 匹配，两个列表都向前推进 */
				fc_i++;
				na = na->inchain;
				break;
			case +1:
				/* 仅推进 na；数组可能在后面有匹配 */
				na = na->inchain;
				break;
			default:
				assert(NOTREACHED);
		}
	}
	while (fc_i < fc_arccount)
	{
		/* s 没有匹配的 a */
		struct arc *a = fc_arcarray[fc_i];

		createarc(nfa, a->type, a->co, a->from, fc_s);
		fc_i++;
	}
}

/*
 * moveouts - 将一个状态的所有出弧移动到另一个状态
 *
 * 请参见 moveins() 的注释
 */
static void moveouts(struct nfa *nfa,
		 struct state *fc_oldState,
		 struct state *fc_newState)
{
	assert(fc_oldState != fc_newState);

	if (fc_newState->nouts == 0)
	{
		/* 无需去重 */
		struct arc *fc_a;

		while ((fc_a = fc_oldState->outs) != NULL)
		{
			createarc(nfa, fc_a->type, fc_a->co, fc_newState, fc_a->to);
			freearc(nfa, fc_a);
		}
	}
	else if (!BULK_ARC_OP_USE_SORT(fc_oldState->nouts, fc_newState->nouts))
	{
		/* 当弧不多时，逐个处理它们 */
		struct arc *fc_a;

		while ((fc_a = fc_oldState->outs) != NULL)
		{
			cparc(nfa, fc_a, fc_newState, fc_a->to);
			freearc(nfa, fc_a);
		}
	}
	else
	{
		/*
		 * 当弧很多时，使用排序合并的方法。注意 changearcsource()
		 * 会将弧放到新状态链的前面，因此不会破坏我们
		 * 在链的排序部分的遍历。
		 */
		struct arc *fc_oa;
		struct arc *fc_na;

		/*
		 * 由于我们在这条代码路径中绕过了 newarc()，我们最好
		 * 包含一个取消检查。
		 */
		if (CANCEL_REQUESTED(nfa->v->re))
		{
			NERR(REG_CANCEL);
			return;
		}

		sortouts(nfa, fc_oldState);
		sortouts(nfa, fc_newState);
		if (NISERR())
			return;				/* 可能未能排序 */
		fc_oa = fc_oldState->outs;
		fc_na = fc_newState->outs;
		while (fc_oa != NULL && fc_na != NULL)
		{
			struct arc *fc_a = fc_oa;

			switch (sortouts_cmp(&fc_oa, &fc_na))
			{
				case -1:
					/* newState 没有匹配的 oa */
					fc_oa = fc_oa->outchain;

					/*
					 * 与其执行 createarc + freearc，不如直接解除链接
					 * 并重新链接现有的弧结构。
					 */
					changearcsource(fc_a, fc_newState);
					break;
				case 0:
					/* 匹配，两个列表都向前推进 */
					fc_oa = fc_oa->outchain;
					fc_na = fc_na->outchain;
					/* ... 并从 oldState 中删除重复弧 */
					freearc(nfa, fc_a);
					break;
				case +1:
					/* 仅推进 na； oa 可能在后面有匹配 */
					fc_na = fc_na->outchain;
					break;
				default:
					assert(NOTREACHED);
			}
		}
		while (fc_oa != NULL)
		{
			/* newState 没有匹配的 oa */
			struct arc *fc_a = fc_oa;

			fc_oa = fc_oa->outchain;
			changearcsource(fc_a, fc_newState);
		}
	}

	assert(fc_oldState->nouts == 0);
	assert(fc_oldState->outs == NULL);
}

/*
 * copyouts - 将一个状态的出弧复制到另一个状态
 *
 * 请参见 copyins() 的注释
 */
static void copyouts(struct nfa *nfa,
		 struct state *fc_oldState,
		 struct state *fc_newState)
{
	assert(fc_oldState != fc_newState);
	assert(fc_newState->nouts == 0);	/* 请参见上面的注释 */

	if (fc_newState->nouts == 0)
	{
		/* 无需去重 */
		struct arc *fc_a;

		for (fc_a = fc_oldState->outs; fc_a != NULL; fc_a = fc_a->outchain)
			createarc(nfa, fc_a->type, fc_a->co, fc_newState, fc_a->to);
	}
#ifdef NOT_USED					/* 请参见上面的注释 */
	else if (!BULK_ARC_OP_USE_SORT(fc_oldState->nouts, fc_newState->nouts))
	{
		/* 当弧不多时，逐个处理它们 */
		struct arc *fc_a;

		for (fc_a = fc_oldState->outs; fc_a != NULL; fc_a = fc_a->outchain)
			cparc(nfa, fc_a, fc_newState, fc_a->to);
	}
	else
	{
		/*
		 * 当弧很多时，使用排序合并的方法。注意 createarc()
		 * 会将新弧放到新状态链的前面，因此不会破坏我们
		 * 在链的排序部分的遍历。
		 */
		struct arc *fc_oa;
		struct arc *fc_na;

		/*
		 * 由于我们在这条代码路径中绕过了 newarc()，我们最好
		 * 包含一个取消检查。
		 */
		if (CANCEL_REQUESTED(nfa->v->re))
		{
			NERR(REG_CANCEL);
			return;
		}

		sortouts(nfa, fc_oldState);
		sortouts(nfa, fc_newState);
		if (NISERR())
			return;				/* 可能未能排序 */
		fc_oa = fc_oldState->outs;
		fc_na = fc_newState->outs;
		while (fc_oa != NULL && fc_na != NULL)
		{
			struct arc *fc_a = fc_oa;

			switch (sortouts_cmp(&fc_oa, &fc_na))
			{
				case -1:
					/* newState 没有匹配的 oa */
					fc_oa = fc_oa->outchain;
					createarc(nfa, fc_a->type, fc_a->co, fc_newState, fc_a->to);
					break;
				case 0:
					/* 匹配，两个列表都向前推进 */
					fc_oa = fc_oa->outchain;
					fc_na = fc_na->outchain;
					break;
				case +1:
					/* 仅推进 na； oa 可能在后面有匹配 */
					fc_na = fc_na->outchain;
					break;
				default:
					assert(NOTREACHED);
			}
		}
		while (fc_oa != NULL)
		{
			/* newState 没有匹配的 oa */
			struct arc *fc_a = fc_oa;

			fc_oa = fc_oa->outchain;
			createarc(nfa, fc_a->type, fc_a->co, fc_newState, fc_a->to);
		}
	}
#endif							/* 在较旧的 Perl 上值得怀疑... */
}

/*
 * cloneouts - 将一个状态的出弧复制到另一个状态对，修改类型
 *
 * 这仅用于将简单弧转换为前后弧，它们共享“co”的相同解释。
 * 对于 LACON 来说，这没有意义。
 */
static void cloneouts(struct nfa *nfa,
		  struct state *fc_old,
		  struct state *fc_from,
		  struct state *fc_to,
		  int fc_type)
{
	struct arc *fc_a;

	assert(fc_old != fc_from);
	assert(fc_type == AHEAD || fc_type == BEHIND);

	for (fc_a = fc_old->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		assert(fc_a->type == PLAIN);
		newarc(nfa, fc_type, fc_a->co, fc_from, fc_to);
	}
}

/*
 * delsub - 删除一个子 NFA，如果必要，更新 subre 指针
 *
 * 这使用递归遍历子 NFA，使用它们的 tmp 指针标记已查看的状态。
 */
static void delsub(struct nfa *nfa,
	   struct state *fc_lp,		/* 子 NFA 从这里开始... */
	   struct state *fc_rp)		/* ...到这里，不包括 */
{
	assert(fc_lp != fc_rp);

	fc_rp->tmp = fc_rp;				/* mark end */

	deltraverse(nfa, fc_lp, fc_lp);
	if (NISERR())
		return;					/* 断言在失败后可能不成立 */
	assert(fc_lp->nouts == 0 && fc_rp->nins == 0);	/* 完成了工作 */
	assert(fc_lp->no != FREESTATE && fc_rp->no != FREESTATE); /* no more */

	fc_rp->tmp = NULL;				/* 取消标记结束 */
	fc_lp->tmp = NULL;				/* 并开始，由 deltraverse 标记 */
}

/*
 * deltraverse - delsub 的递归核心
 * 这个例程的基本任务是销毁状态的所有出弧。
 */
static void deltraverse(struct nfa *nfa,
			struct state *fc_leftend,
			struct state *fc_s)
{
	struct arc *fc_a;
	struct state *fc_to;

	/* 由于这是递归的，它可能导致堆栈溢出 */
	if (STACK_TOO_DEEP(nfa->v->re))
	{
		NERR(REG_ETOOBIG);
		return;
	}

	if (fc_s->nouts == 0)
		return;					/* 无需操作 */
	if (fc_s->tmp != NULL)
		return;					/* 已经在进行中 */

	fc_s->tmp = fc_s;					/* 标记为进行中 */

	while ((fc_a = fc_s->outs) != NULL)
	{
		fc_to = fc_a->to;
		deltraverse(nfa, fc_leftend, fc_to);
		if (NISERR())
			return;				/* 断言在失败后可能不成立 */
		assert(fc_to->nouts == 0 || fc_to->tmp != NULL);
		freearc(nfa, fc_a);
		if (fc_to->nins == 0 && fc_to->tmp == NULL)
		{
			assert(fc_to->nouts == 0);
			freestate(nfa, fc_to);
		}
	}

	assert(fc_s->no != FREESTATE); /* 我们仍然在这里 */
	assert(fc_s == fc_leftend || fc_s->nins != 0);	/* 并且仍然可达 */
	assert(fc_s->nouts == 0);		/* 但没有出弧 */

	fc_s->tmp = NULL;				/* 我们在这里完成了 */
}

/*
 * dupnfa - 复制子-NFA
 *
 * 另一个递归遍历，这次使用 tmp 指向副本
 * 并且标记已经看到的状态。你知道它是状态指针的原因了吗？:-)
 */
static void dupnfa(struct nfa *nfa,
	   struct state *fc_start,		/* 从这里开始的子NFA的副本 */
	   struct state *fc_stop,		/* 并在这里停止 */
	   struct state *fc_from,		/* 从这里串联副本 */
	   struct state *fc_to)		/* to here */
{
	if (fc_start == fc_stop)
	{
		newarc(nfa, EMPTY, 0, fc_from, fc_to);
		return;
	}

	fc_stop->tmp = fc_to;
	duptraverse(nfa, fc_start, fc_from);
	/* 完成，除了清除 tmp 指针 */

	fc_stop->tmp = NULL;
	cleartraverse(nfa, fc_start);
}

/*
 * duptraverse - dupnfa 的递归核心
 */
static void duptraverse(struct nfa *nfa,
			struct state *fc_s,
			struct state *fc_stmp) /* s 的副本，或 NULL */
{
	struct arc *fc_a;

	/* 由于这是递归的，它可能导致堆栈溢出 */
	if (STACK_TOO_DEEP(nfa->v->re))
	{
		NERR(REG_ETOOBIG);
		return;
	}

	if (fc_s->tmp != NULL)
		return;					/* 已经完成 */

	fc_s->tmp = (fc_stmp == NULL) ? newstate(nfa) : fc_stmp;
	if (fc_s->tmp == NULL)
	{
		assert(NISERR());
		return;
	}

	for (fc_a = fc_s->outs; fc_a != NULL && !NISERR(); fc_a = fc_a->outchain)
	{
		duptraverse(nfa, fc_a->to, (struct state *) NULL);
		if (NISERR())
			break;
		assert(fc_a->to->tmp != NULL);
		cparc(nfa, fc_a, fc_s->tmp, fc_a->to->tmp);
	}
}

/*
 * removeconstraints - 删除 NFA 中的任何约束
 *
 * 约束弧被空弧替换，实际上将所有
 * 约束视为自动满足。
 */
static void removeconstraints(struct nfa *nfa,
				  struct state *fc_start,	/* 从这里开始处理 subNFA */
				  struct state *fc_stop)	/* 并在这里停止 */
{
	if (fc_start == fc_stop)
		return;

	fc_stop->tmp = fc_stop;
	removetraverse(nfa, fc_start);
	/* 完成，除了清除 tmp 指针 */

	fc_stop->tmp = NULL;
	cleartraverse(nfa, fc_start);
}

/*
 * removetraverse - removeconstraints 的递归核心
 */
static void removetraverse(struct nfa *nfa,
			   struct state *fc_s)
{
	struct arc *fc_a;
	struct arc *fc_oa;

	/* 由于这是递归的，它可能导致堆栈溢出 */
	if (STACK_TOO_DEEP(nfa->v->re))
	{
		NERR(REG_ETOOBIG);
		return;
	}

	if (fc_s->tmp != NULL)
		return;					/* 已经完成 */

	fc_s->tmp = fc_s;
	for (fc_a = fc_s->outs; fc_a != NULL && !NISERR(); fc_a = fc_oa)
	{
		removetraverse(nfa, fc_a->to);
		if (NISERR())
			break;
		fc_oa = fc_a->outchain;
		switch (fc_a->type)
		{
			case PLAIN:
			case EMPTY:
			case CANTMATCH:
				/* 无需操作 */
				break;
			case AHEAD:
			case BEHIND:
			case '^':
			case '$':
			case LACON:
				/* 替换它 */
				newarc(nfa, EMPTY, 0, fc_s, fc_a->to);
				freearc(nfa, fc_a);
				break;
			default:
				NERR(REG_ASSERT);
				break;
		}
	}
}

/*
 * cleartraverse - 为留下 tmp 指针的算法进行递归清理
 */
static void cleartraverse(struct nfa *nfa,
			  struct state *fc_s)
{
	struct arc *fc_a;

	/* 由于这是递归的，它可能导致堆栈溢出 */
	if (STACK_TOO_DEEP(nfa->v->re))
	{
		NERR(REG_ETOOBIG);
		return;
	}

	if (fc_s->tmp == NULL)
		return;
	fc_s->tmp = NULL;

	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
		cleartraverse(nfa, fc_a->to);
}

/*
 * single_color_transition - 从 s1 到 s2 是否跨越一个 PLAIN 弧？
 *
 * 如果从 s1 到 s2 的遍历需要一个单一的 PLAIN 匹配（可能是任何
 * 一组颜色），则返回一个其出弧列表仅包含这些颜色的 PLAIN 弧的状态。
 * 否则返回 NULL。
 *
 * 这在优化 NFA 之前使用，因此可能会有 EMPTY 弧，我们应该忽略；EMPTY 的可能性就是结果状态可能
 * 与 s1 不同的原因。
 *
 * 在这里处理多个平行的 PLAIN 弧是值得麻烦的，因为像 [abc] 这样的括号构造
 * 可能产生一个或多个平行的 PLAIN 弧，这取决于表达式中早期的原子。
 * 我们更希望这个实现细节不会造成用户可见的性能差异。
 */
static struct state *
single_color_transition(struct state *fc_s1, struct state *fc_s2)
{
	struct arc *fc_a;

	/* 忽略前导 EMPTY 弧（如果有的话） */
	if (fc_s1->nouts == 1 && fc_s1->outs->type == EMPTY)
		fc_s1 = fc_s1->outs->to;
	/* 同样忽略任何尾随 EMPTY 弧 */
	if (fc_s2->nins == 1 && fc_s2->ins->type == EMPTY)
		fc_s2 = fc_s2->ins->from;
	/* 如果中间可能有一个单状态的循环，则拒绝 */
	if (fc_s1 == fc_s2)
		return NULL;
	/* s1 至少必须有一个出弧... */
	if (fc_s1->outs == NULL)
		return NULL;
	/* ...并且它们必须都是到 s2 的 PLAIN 弧 */
	for (fc_a = fc_s1->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		if (fc_a->type != PLAIN || fc_a->to != fc_s2)
			return NULL;
	}
	/* 好的，返回 s1 作为相关出弧的拥有者 */
	return fc_s1;
}

/*
 * specialcolors - 为 NFA 填充特殊颜色
 */
static void specialcolors(struct nfa *nfa)
{
	/* BOS、BOL、EOS、EOL 的假颜色 */
	if (nfa->parent == NULL)
	{
		nfa->bos[0] = pseudocolor(nfa->cm);
		nfa->bos[1] = pseudocolor(nfa->cm);
		nfa->eos[0] = pseudocolor(nfa->cm);
		nfa->eos[1] = pseudocolor(nfa->cm);
	}
	else
	{
		assert(nfa->parent->bos[0] != COLORLESS);
		nfa->bos[0] = nfa->parent->bos[0];
		assert(nfa->parent->bos[1] != COLORLESS);
		nfa->bos[1] = nfa->parent->bos[1];
		assert(nfa->parent->eos[0] != COLORLESS);
		nfa->eos[0] = nfa->parent->eos[0];
		assert(nfa->parent->eos[1] != COLORLESS);
		nfa->eos[1] = nfa->parent->eos[1];
	}
}

/*
 * optimize - 优化 NFA
 *
 * 此函数的主要目标不是“优化”（尽管它确实试图消除无用的 NFA 状态），而是将 NFA 缩减到正则表达式执行器可以处理的形式。执行器，以及其输入的 cNFA 格式，只能处理 PLAIN 和 LACON 弧。正则表达式解析器的输出还包括 EMPTY（无操作）弧，以及 ^、$、AHEAD 和 BEHIND 约束弧，我们必须在此处去除。我们首先去除 EMPTY 弧，然后处理约束弧。任何一个工作的最难部分是去除目标弧类型的循环。无论如何我们都必须这样做，因为这样的循环会允许执行器在循环中无休止地循环，而无法在输入字符串中取得任何进展。
 */
static long						/* re_info 位 */
optimize(struct nfa *nfa,
		 FILE *fc_f)				/* 用于调试输出；NULL 无 */
{
#ifdef REG_DEBUG
	int			fc_verbose = (fc_f != NULL) ? 1 : 0;

	if (fc_verbose)
		fprintf(fc_f, "\ninitial cleanup:\n");
#endif
	/* 如果我们有任何 CANTMATCH 弧，就去掉它们；但这不常见 */
	if (nfa->flags & HASCANTMATCH)
	{
		removecantmatch(nfa);
		nfa->flags &= ~HASCANTMATCH;
	}
	cleanup(nfa);				/* 可能简化情况 */
#ifdef REG_DEBUG
	if (fc_verbose)
		dumpnfa(nfa, fc_f);
	if (fc_verbose)
		fprintf(fc_f, "\nempties:\n");
#endif
	fixempties(nfa, fc_f);			/* 去掉 EMPTY 弧 */
#ifdef REG_DEBUG
	if (fc_verbose)
		fprintf(fc_f, "\nconstraints:\n");
#endif
	fixconstraintloops(nfa, fc_f); /* 去掉约束循环 */
	pullback(nfa, fc_f);			/* 向后拉回约束 */
	pushfwd(nfa, fc_f);			/* 向前推进约束 */
#ifdef REG_DEBUG
	if (fc_verbose)
		fprintf(fc_f, "\nfinal cleanup:\n");
#endif
	cleanup(nfa);				/* 最终整理 */
#ifdef REG_DEBUG
	if (fc_verbose)
		dumpnfa(nfa, fc_f);
#endif
	return analyze(nfa);		/* 以及分析 */
}

/*
 * pullback - 向后拉回约束以消除它们
 */
static void pullback(struct nfa *nfa,
		 FILE *fc_f)				/* 用于调试输出；NULL 无 */
{
	struct state *fc_s;
	struct state *fc_nexts;
	struct arc *fc_a;
	struct arc *fc_nexta;
	struct state *fc_intermediates;
	int			fc_progress;

	/* 查找并拉动，直到没有更多 */
	do
	{
		fc_progress = 0;
		for (fc_s = nfa->states; fc_s != NULL && !NISERR(); fc_s = fc_nexts)
		{
			fc_nexts = fc_s->next;
			fc_intermediates = NULL;
			for (fc_a = fc_s->outs; fc_a != NULL && !NISERR(); fc_a = fc_nexta)
			{
				fc_nexta = fc_a->outchain;
				if (fc_a->type == '^' || fc_a->type == BEHIND)
					if (pull(nfa, fc_a, &fc_intermediates))
						fc_progress = 1;
			}
			/* 清除这里创建的中间状态的临时字段 */
			while (fc_intermediates != NULL)
			{
				struct state *ns = fc_intermediates->tmp;

				fc_intermediates->tmp = NULL;
				fc_intermediates = ns;
			}
			/* 如果 s 现在无用，去掉它 */
			if ((fc_s->nins == 0 || fc_s->nouts == 0) && !fc_s->flag)
				dropstate(nfa, fc_s);
		}
		if (fc_progress && fc_f != NULL)
			dumpnfa(nfa, fc_f);
	} while (fc_progress && !NISERR());
	if (NISERR())
		return;

	/*
	 * 我们能够拉到起始状态的任何 ^ 约束现在可以用引用 BOS 或 BOL 颜色的 PLAIN 弧替换。不过，NFA 中不应该还有其他 ^ 或 BEHIND 弧，尽管我们在此处不检查（如果是的话，compact() 将会失败）。
	 */
	for (fc_a = nfa->pre->outs; fc_a != NULL; fc_a = fc_nexta)
	{
		fc_nexta = fc_a->outchain;
		if (fc_a->type == '^')
		{
			assert(fc_a->co == 0 || fc_a->co == 1);
			newarc(nfa, PLAIN, nfa->bos[fc_a->co], fc_a->from, fc_a->to);
			freearc(nfa, fc_a);
		}
	}
}

/*
 * pull - 将后约束向后拉过其源状态
 *
 * 如果成功则返回 1（除非源是起始状态或发生内部错误，它总是成功），如果没有发生任何事情则返回 0。
 *
 * 此函数的一个重要特性是它不删除任何预先存在的状态，也不删除约束的源状态的任何出弧，除了给定的约束弧。这使得 pullback() 中的循环是安全的，代价是我们可能会留下无用的状态。因此，我们将删除这些状态的工作留给 pullback()。
 *
 * 如果源状态具有多个后约束出弧，和/或多个兼容的约束入弧，我们只需为每个前驱和后继状态的组合创建一个新的中间状态。*intermediates 指向该源状态的此类中间状态的列表（通过它们的临时字段链在一起）。
 */
static int pull(struct nfa *nfa,
	 struct arc *fc_con,
	 struct state **fc_intermediates)
{
	struct state *fc_from = fc_con->from;
	struct state *fc_to = fc_con->to;
	struct arc *fc_a;
	struct arc *fc_nexta;
	struct state *fc_s;

	assert(fc_from != fc_to);			/* 应该早点处理掉这个 */
	if (fc_from->flag)				/* 不能向回拉动超过起始状态 */
		return 0;
	if (fc_from->nins == 0)
	{							/* unreachable */
		freearc(nfa, fc_con);
		return 1;
	}

	/*
	 * 首先，如果需要，克隆源状态以避免其他出弧。这可能看起来浪费，但这简化了逻辑，而且我们将在底部再次处理掉克隆状态。
	 */
	if (fc_from->nouts > 1)
	{
		fc_s = newstate(nfa);
		if (NISERR())
			return 0;
		copyins(nfa, fc_from, fc_s);	/* 复制入弧 */
		cparc(nfa, fc_con, fc_s, fc_to); /* 移动约束弧 */
		freearc(nfa, fc_con);
		if (NISERR())
			return 0;
		fc_from = fc_s;
		fc_con = fc_from->outs;
	}
	assert(fc_from->nouts == 1);

	/* 将约束传播到源状态的入弧中 */
	for (fc_a = fc_from->ins; fc_a != NULL && !NISERR(); fc_a = fc_nexta)
	{
		fc_nexta = fc_a->inchain;
		switch (combine(nfa, fc_con, fc_a))
		{
			case INCOMPATIBLE:	/* 销毁该弧 */
				freearc(nfa, fc_a);
				break;
			case SATISFIED:		/* 无需采取行动 */
				break;
			case COMPATIBLE:	/* 交换两个弧，或多或少 */
				/* 需要一个中间状态，但可能已经有一个了 */
				for (fc_s = *fc_intermediates; fc_s != NULL; fc_s = fc_s->tmp)
				{
					assert(fc_s->nins > 0 && fc_s->nouts > 0);
					if (fc_s->ins->from == fc_a->from && fc_s->outs->to == fc_to)
						break;
				}
				if (fc_s == NULL)
				{
					fc_s = newstate(nfa);
					if (NISERR())
						return 0;
					fc_s->tmp = *fc_intermediates;
					*fc_intermediates = fc_s;
				}
				cparc(nfa, fc_con, fc_a->from, fc_s);
				cparc(nfa, fc_a, fc_s, fc_to);
				freearc(nfa, fc_a);
				break;
			case REPLACEARC:	/* 替换弧的颜色 */
				newarc(nfa, fc_a->type, fc_con->co, fc_a->from, fc_to);
				freearc(nfa, fc_a);
				break;
			default:
				assert(NOTREACHED);
				break;
		}
	}

	/* 剩余的入弧（如果有的话），纳入约束 */
	moveins(nfa, fc_from, fc_to);
	freearc(nfa, fc_con);
	/* 从状态现在已无用，但我们留给pullback()去清理 */
	return 1;
}

/*
 * pushfwd - 将约束向前推进以消除它们
 */
static void pushfwd(struct nfa *nfa,
		FILE *fc_f)				/* 用于调试输出；NULL 无 */
{
	struct state *fc_s;
	struct state *fc_nexts;
	struct arc *fc_a;
	struct arc *fc_nexta;
	struct state *fc_intermediates;
	int			fc_progress;

	/* 查找并推进，直到没有更多 */
	do
	{
		fc_progress = 0;
		for (fc_s = nfa->states; fc_s != NULL && !NISERR(); fc_s = fc_nexts)
		{
			fc_nexts = fc_s->next;
			fc_intermediates = NULL;
			for (fc_a = fc_s->ins; fc_a != NULL && !NISERR(); fc_a = fc_nexta)
			{
				fc_nexta = fc_a->inchain;
				if (fc_a->type == '$' || fc_a->type == AHEAD)
					if (push(nfa, fc_a, &fc_intermediates))
						fc_progress = 1;
			}
			/* 清除这里创建的中间状态的临时字段 */
			while (fc_intermediates != NULL)
			{
				struct state *ns = fc_intermediates->tmp;

				fc_intermediates->tmp = NULL;
				fc_intermediates = ns;
			}
			/* 如果 s 现在无用，去掉它 */
			if ((fc_s->nins == 0 || fc_s->nouts == 0) && !fc_s->flag)
				dropstate(nfa, fc_s);
		}
		if (fc_progress && fc_f != NULL)
			dumpnfa(nfa, fc_f);
	} while (fc_progress && !NISERR());
	if (NISERR())
		return;

	/*
	 * 我们能够推进到后状态的任何 $ 约束现在可以用引用EOS或EOL颜色的
	 * PLAIN弧替换。NFA中不应留下其他$或AHEAD弧，尽管我们在此不检查
	 * （如果是这样，compact()会失败）。
	 */
	for (fc_a = nfa->post->ins; fc_a != NULL; fc_a = fc_nexta)
	{
		fc_nexta = fc_a->inchain;
		if (fc_a->type == '$')
		{
			assert(fc_a->co == 0 || fc_a->co == 1);
			newarc(nfa, PLAIN, nfa->eos[fc_a->co], fc_a->from, fc_a->to);
			freearc(nfa, fc_a);
		}
	}
}

/*
 * push - 将前向约束推进到其目标状态之外
 *
 * 如果成功（除非目标是后状态或我们有内部错误），则返回1（这总是成功），
 * 如果没有发生任何事，返回0。
 *
 * 此函数的一个显著特性是它不会删除任何预先存在的
 * 状态，也不会删除约束的到达状态的任何入弧，除了给定的约束弧。这确保了
 * pushfwd()中的循环安全，代价是我们可能会留下一些无用的状态。因此，
 * 我们留给pushfwd()去删除这些状态。
 *
 * 如果到达状态有多个前向约束入弧和/或多个兼容的约束出弧，
 * 我们只需为每个前驱和后继状态的组合创建一个新的中间状态。*intermediates
 * 指向此到达状态的中间状态列表（通过它们的tmp字段进行链接）。
 */
static int push(struct nfa *nfa,
	 struct arc *fc_con,
	 struct state **fc_intermediates)
{
	struct state *fc_from = fc_con->from;
	struct state *fc_to = fc_con->to;
	struct arc *fc_a;
	struct arc *fc_nexta;
	struct state *fc_s;

	assert(fc_to != fc_from);			/* 应该早点处理掉这个 */
	if (fc_to->flag)				/* 不能向前推进超出结束 */
		return 0;
	if (fc_to->nouts == 0)
	{							/* dead end */
		freearc(nfa, fc_con);
		return 1;
	}

	/*
	 * 首先，如果需要，克隆到达状态以避免其他入弧。这看似浪费，
	 * 但它简化了逻辑，我们将在底部再次删除克隆状态。
	 */
	if (fc_to->nins > 1)
	{
		fc_s = newstate(nfa);
		if (NISERR())
			return 0;
		copyouts(nfa, fc_to, fc_s);	/* 复制出弧 */
		cparc(nfa, fc_con, fc_from, fc_s);	/* 移动约束弧 */
		freearc(nfa, fc_con);
		if (NISERR())
			return 0;
		fc_to = fc_s;
		fc_con = fc_to->ins;
	}
	assert(fc_to->nins == 1);

	/* 将约束传播到到达状态的出弧中 */
	for (fc_a = fc_to->outs; fc_a != NULL && !NISERR(); fc_a = fc_nexta)
	{
		fc_nexta = fc_a->outchain;
		switch (combine(nfa, fc_con, fc_a))
		{
			case INCOMPATIBLE:	/* 销毁该弧 */
				freearc(nfa, fc_a);
				break;
			case SATISFIED:		/* 无需采取行动 */
				break;
			case COMPATIBLE:	/* 交换两个弧，或多或少 */
				/* 需要一个中间状态，但可能已经有一个了 */
				for (fc_s = *fc_intermediates; fc_s != NULL; fc_s = fc_s->tmp)
				{
					assert(fc_s->nins > 0 && fc_s->nouts > 0);
					if (fc_s->ins->from == fc_from && fc_s->outs->to == fc_a->to)
						break;
				}
				if (fc_s == NULL)
				{
					fc_s = newstate(nfa);
					if (NISERR())
						return 0;
					fc_s->tmp = *fc_intermediates;
					*fc_intermediates = fc_s;
				}
				cparc(nfa, fc_con, fc_s, fc_a->to);
				cparc(nfa, fc_a, fc_from, fc_s);
				freearc(nfa, fc_a);
				break;
			case REPLACEARC:	/* 替换弧的颜色 */
				newarc(nfa, fc_a->type, fc_con->co, fc_from, fc_a->to);
				freearc(nfa, fc_a);
				break;
			default:
				assert(NOTREACHED);
				break;
		}
	}

	/* 剩余的出弧（如果有的话），纳入约束 */
	moveouts(nfa, fc_to, fc_from);
	freearc(nfa, fc_con);
	/* 到达状态现在已无用，但我们留给pushfwd()去清理 */
	return 1;
}

/*
 * combine - 约束落在弧上，会发生什么？
 *
 * #def INCOMPATIBLE	1	// 销毁弧
 * #def SATISFIED		2	// 约束满足
 * #def COMPATIBLE		3	// 兼容但尚未满足
 * #def REPLACEARC		4	// 用约束颜色替换弧的颜色
 */
static int combine(struct nfa *nfa,
		struct arc *fc_con,
		struct arc *fc_a)
{
#define  CA(ct,at)	 (((ct)<<CHAR_BIT) | (at))

	switch (CA(fc_con->type, fc_a->type))
	{
		case CA('^', PLAIN):	/* 换行符单独处理 */
		case CA('$', PLAIN):
			return INCOMPATIBLE;
			break;
		case CA(AHEAD, PLAIN):	/* 颜色约束遇到颜色 */
		case CA(BEHIND, PLAIN):
			if (fc_con->co == fc_a->co)
				return SATISFIED;
			if (fc_con->co == RAINBOW)
			{
				/* 除非弧的颜色是伪颜色，否则约束满足 */
				if (!(nfa->cm->cd[fc_a->co].flags & PSEUDO))
					return SATISFIED;
			}
			else if (fc_a->co == RAINBOW)
			{
				/* 如果约束是伪颜色，则不兼容 */
				/* （这是假设；我们今天没有这样的约束） */
				if (nfa->cm->cd[fc_con->co].flags & PSEUDO)
					return INCOMPATIBLE;
				/* 否则，约束将弧限制为仅是其颜色 */
				return REPLACEARC;
			}
			return INCOMPATIBLE;
			break;
		case CA('^', '^'):		/* 碰撞，类似的约束 */
		case CA('$', '$'):
			if (fc_con->co == fc_a->co)	/* 真正的重复 */
				return SATISFIED;
			return INCOMPATIBLE;
			break;
		case CA(AHEAD, AHEAD):	/* 碰撞，类似的约束 */
		case CA(BEHIND, BEHIND):
			if (fc_con->co == fc_a->co)	/* 真正的重复 */
				return SATISFIED;
			if (fc_con->co == RAINBOW)
			{
				/* 除非弧的颜色是伪颜色，否则约束满足 */
				if (!(nfa->cm->cd[fc_a->co].flags & PSEUDO))
					return SATISFIED;
			}
			else if (fc_a->co == RAINBOW)
			{
				/* 如果约束是伪颜色，则不兼容 */
				/* （这是假设；我们今天没有这样的约束） */
				if (nfa->cm->cd[fc_con->co].flags & PSEUDO)
					return INCOMPATIBLE;
				/* 否则，约束将弧限制为仅是其颜色 */
				return REPLACEARC;
			}
			return INCOMPATIBLE;
			break;
		case CA('^', BEHIND):	/* 碰撞，不同的约束 */
		case CA(BEHIND, '^'):
		case CA('$', AHEAD):
		case CA(AHEAD, '$'):
			return INCOMPATIBLE;
			break;
		case CA('^', '$'):		/* 约束相互通过 */
		case CA('^', AHEAD):
		case CA(BEHIND, '$'):
		case CA(BEHIND, AHEAD):
		case CA('$', '^'):
		case CA('$', BEHIND):
		case CA(AHEAD, '^'):
		case CA(AHEAD, BEHIND):
		case CA('^', LACON):
		case CA(BEHIND, LACON):
		case CA('$', LACON):
		case CA(AHEAD, LACON):
			return COMPATIBLE;
			break;
	}
	assert(NOTREACHED);
	return INCOMPATIBLE;		/* 为了盲编译器的利益 */
}

/*
 * fixempties - 消除EMPTY弧
 */
static void fixempties(struct nfa *nfa,
		   FILE *fc_f)				/* 用于调试输出；NULL 无 */
{
	struct state *fc_s;
	struct state *fc_s2;
	struct state *fc_nexts;
	struct arc *fc_a;
	struct arc *fc_nexta;
	int			fc_totalinarcs;
	struct arc **fc_inarcsorig;
	struct arc **fc_arcarray;
	int			fc_arccount;
	int			fc_prevnins;
	int			fc_nskip;

	/*
	 * 首先，消除任何唯一出弧为EMPTY的状态，因为
	 * 它们基本上只是其后继的别名。解析算法创建了足够多的这些，
	 * 以至于值得特别处理这种情况。
	 */
	for (fc_s = nfa->states; fc_s != NULL && !NISERR(); fc_s = fc_nexts)
	{
		fc_nexts = fc_s->next;
		if (fc_s->flag || fc_s->nouts != 1)
			continue;
		fc_a = fc_s->outs;
		assert(fc_a != NULL && fc_a->outchain == NULL);
		if (fc_a->type != EMPTY)
			continue;
		if (fc_s != fc_a->to)
			moveins(nfa, fc_s, fc_a->to);
		dropstate(nfa, fc_s);
	}

	/*
	 * 同样，通过将其折叠到前驱中，消除任何唯一的EMPTY入弧的状态。
	 */
	for (fc_s = nfa->states; fc_s != NULL && !NISERR(); fc_s = fc_nexts)
	{
		fc_nexts = fc_s->next;
		/* 在我们这样做的时候，确保tmp字段为下一步清空 */
		assert(fc_s->tmp == NULL);
		if (fc_s->flag || fc_s->nins != 1)
			continue;
		fc_a = fc_s->ins;
		assert(fc_a != NULL && fc_a->inchain == NULL);
		if (fc_a->type != EMPTY)
			continue;
		if (fc_s != fc_a->from)
			moveouts(nfa, fc_s, fc_a->from);
		dropstate(nfa, fc_s);
	}

	if (NISERR())
		return;

	/*
	 * 对于每个剩余的NFA状态，找到所有可以通过一个或多个EMPTY弧到达的其他状态。
	 * 然后生成新的弧，消除每条这样的链的需要。
	 *
	 * 我们可以通过将非EMPTY弧向前推进（直接链接“from”状态的前驱到“to”状态）或
	 * 将它们向后拉（直接链接“from”到“to”的后继状态）来替换从“from”状态到“to”状态的
	 * EMPTY弧链。我们选择总是执行前者；这个选择有些任意，但下面的方法需要我们
	 * 均匀地做其中之一。
	 *
	 * 假设我们有一条N个连续的EMPTY弧链（其中N很容易接近NFA的大小）。所有中间状态
	 * 必须有额外的入弧和出弧，否则它们会在上述步骤中被移除。假设它们的入弧大多不是
	 * EMPTY的，我们将向NFA添加O(N^2)条弧，因为任何一个状态链中的非EMPTY入弧必须
	 * 被复制为指向它的所有后继状态。因此，没有希望做少于O(N^2)的工作；然而，我们应该
	 * 努力保持大O成本不至于变得更糟，否则在没有注意的情况下容易变得更糟。
	 * 特别是，假设我们将所有S1的入弧向前复制到S2，然后也复制到S3，随后考虑将S2的
	 * 入弧向前推送到S3。如果我们在这其中包括已经从S1复制的弧，我们将做O(N^3)的工作。
	 * （内置于newarc()及其同伴中的重复弧消除将去除额外的弧，但代价不小。）
	 *
	 * 我们可以通过仅处理在此阶段开始时存在的弧作为候选向前推进的弧来避免这个成本。
	 * 为了识别那些弧，我们记住每个状态最初必须拥有的第一个入弧。我们依赖于newarc()
	 * 和朋友把新弧放到它们的目标状态的入链的前面，并且此阶段绝不删除弧，因此原始弧
	 * 必须是它们目标状态的入链中的最后一条弧。
	 *
	 * 所以这里的过程是，对于NFA中的每个状态，我们收集所有可以通过EMPTY弧到达目标状态
	 * 的状态的非EMPTY入弧。然后我们对这些弧进行排序、去重并合并到目标状态的入链中。
	 * （只要在我们添加弧后更新每个状态的原始弧指针，我们可以安全地使用排序合并；
	 * mergeins的排序步骤可能改变了旧弧的顺序。）
	 *
	 * 另一个值得改进的地方是，由于我们在此阶段仅添加非EMPTY弧，并且所有添加的弧与
	 * 它们克隆的非EMPTY弧具有相同的from状态，我们提前知道任何仅具有EMPTY出弧的状态
	 * 在我们删除EMPTY弧后将因缺乏出弧而变得无用。 （如果它们最开始没有非EMPTY出弧，
	 * 那么它们无法获得非EMPTY出弧。）因此，我们完全不需要更新这些状态的入链。
	 */

	/* 记住状态的第一个原始入弧 */
	/* ...同时计算一下总共有多少个旧入弧 */
	fc_inarcsorig = (struct arc **) MALLOC(nfa->nstates * sizeof(struct arc *));
	if (fc_inarcsorig == NULL)
	{
		NERR(REG_ESPACE);
		return;
	}
	fc_totalinarcs = 0;
	for (fc_s = nfa->states; fc_s != NULL; fc_s = fc_s->next)
	{
		fc_inarcsorig[fc_s->no] = fc_s->ins;
		fc_totalinarcs += fc_s->nins;
	}

	/*
	 * 创建一个工作空间，用于累积要添加到当前目标状态的入弧。
	 * totalinarcs可能是所需空间的相当高估，但在此时NFA不太可能大
	 * 到值得更聪明。
	 *
	 * 注意：totalinarcs可以是零，一些机器对malloc(0)返回NULL。
	 * 如果是这样，请勿抛出错误。
	 */
	fc_arcarray = (struct arc **) MALLOC(fc_totalinarcs * sizeof(struct arc *));
	if (fc_arcarray == NULL && fc_totalinarcs != 0)
	{
		NERR(REG_ESPACE);
		FREE(fc_inarcsorig);
		return;
	}

	/* 并迭代目标状态 */
	for (fc_s = nfa->states; fc_s != NULL && !NISERR(); fc_s = fc_s->next)
	{
		/* 根据上面的说明忽略没有非EMPTY出弧的目标状态 */
		if (!fc_s->flag && !hasnonemptyout(fc_s))
			continue;

		/* 查找前驱状态并累积它们的原始入弧 */
		fc_arccount = 0;
		for (fc_s2 = emptyreachable(nfa, fc_s, fc_s, fc_inarcsorig); fc_s2 != fc_s; fc_s2 = fc_nexts)
		{
			/* 将s2的原始入弧添加到arcarray[]中，但忽略空弧 */
			for (fc_a = fc_inarcsorig[fc_s2->no]; fc_a != NULL; fc_a = fc_a->inchain)
			{
				if (fc_a->type != EMPTY)
					fc_arcarray[fc_arccount++] = fc_a;
			}

			/* 在返回时重置tmp字段 */
			fc_nexts = fc_s2->tmp;
			fc_s2->tmp = NULL;
		}
		fc_s->tmp = NULL;
		assert(fc_arccount <= fc_totalinarcs);

		/* 记住这个状态有多少个原始入弧 */
		fc_prevnins = fc_s->nins;

		/* 将非重复的入弧添加到目标状态 */
		mergeins(nfa, fc_s, fc_arcarray, fc_arccount);

		/* 现在我们必须更新状态的inarcsorig指针 */
		fc_nskip = fc_s->nins - fc_prevnins;
		fc_a = fc_s->ins;
		while (fc_nskip-- > 0)
			fc_a = fc_a->inchain;
		fc_inarcsorig[fc_s->no] = fc_a;
	}

	FREE(fc_arcarray);
	FREE(fc_inarcsorig);

	if (NISERR())
		return;

	/*
	 * 现在删除所有的EMPTY弧，因为我们不再需要它们了。
	 */
	for (fc_s = nfa->states; fc_s != NULL; fc_s = fc_s->next)
	{
		for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_nexta)
		{
			fc_nexta = fc_a->outchain;
			if (fc_a->type == EMPTY)
				freearc(nfa, fc_a);
		}
	}

	/*
	 * 并移除任何已经变得无用的状态。（这次清理不是很彻底，
	 * 如果我们试图将其与前一步合并会更加不彻底；但cleanup()会处理
	 * 我们漏掉的任何东西。）
	 */
	for (fc_s = nfa->states; fc_s != NULL; fc_s = fc_nexts)
	{
		fc_nexts = fc_s->next;
		if ((fc_s->nins == 0 || fc_s->nouts == 0) && !fc_s->flag)
			dropstate(nfa, fc_s);
	}

	if (fc_f != NULL)
		dumpnfa(nfa, fc_f);
}


/*
 * emptyreachable - 递归查找所有能通过 EMPTY 弧到达 s 的状态
 *
 * 返回值是找到的最后一个这样的状态。其 tmp 字段链接到倒数第二个这样的状态，以此类推回到 s，这样这些状态可以在不搜索整个 NFA 的情况下被定位。
 *
 * 由于这仅在 fixempties() 中使用，我们传入由该函数维护的 inarcsorig[] 数组。这让我们可以跳过所有新的 inarcs，这些肯定不是 EMPTY 弧。
 *
 * 这里的最大递归深度等于最长无环 EMPTY 弧链的长度，这肯定不超过 NFA 的大小……但这仍然可能足以引起问题。
 */
static struct state *
emptyreachable(struct nfa *nfa,
			   struct state *fc_s,
			   struct state *fc_lastfound,
			   struct arc **fc_inarcsorig)
{
	struct arc *fc_a;

	/* 由于这是递归的，它可能导致堆栈溢出 */
	if (STACK_TOO_DEEP(nfa->v->re))
	{
		NERR(REG_ETOOBIG);
		return fc_lastfound;
	}

	fc_s->tmp = fc_lastfound;
	fc_lastfound = fc_s;
	for (fc_a = fc_inarcsorig[fc_s->no]; fc_a != NULL; fc_a = fc_a->inchain)
	{
		if (fc_a->type == EMPTY && fc_a->from->tmp == NULL)
			fc_lastfound = emptyreachable(nfa, fc_a->from, fc_lastfound, fc_inarcsorig);
	}
	return fc_lastfound;
}

/*
 * isconstraintarc - 检测一个弧是否属于约束类型
 */
static inline int isconstraintarc(struct arc *fc_a)
{
	switch (fc_a->type)
	{
		case '^':
		case '$':
		case BEHIND:
		case AHEAD:
		case LACON:
			return 1;
	}
	return 0;
}

/*
 * hasconstraintout - 状态是否有约束输出弧？
 */
static int hasconstraintout(struct state *fc_s)
{
	struct arc *fc_a;

	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		if (isconstraintarc(fc_a))
			return 1;
	}
	return 0;
}

/*
 * fixconstraintloops - 消除仅包含约束弧的环
 *
 * 仅包含约束弧的状态环是无用的，因为绕环传递不会代表任何向前的进展。此外，这会在 pullback/pushfwd 中导致无限循环，因此我们需要在进行操作之前消除这些环。
 */
static void fixconstraintloops(struct nfa *nfa,
				   FILE *fc_f)		/* 用于调试输出；NULL 无 */
{
	struct state *fc_s;
	struct state *nexts;
	struct arc *fc_a;
	struct arc *fc_nexta;
	int			fc_hasconstraints;

	/*
	 * 在状态自环的平凡情况下，我们可以直接删除约束弧。这值得特殊处理，因为这样的环比包含多个状态的环要常见得多。
	 * 同时，请注意是否有任何约束弧存活。
	 */
	fc_hasconstraints = 0;
	for (fc_s = nfa->states; fc_s != NULL && !NISERR(); fc_s = nexts)
	{
		nexts = fc_s->next;
		/* 在我们这样做的时候，确保tmp字段为下一步清空 */
		assert(fc_s->tmp == NULL);
		for (fc_a = fc_s->outs; fc_a != NULL && !NISERR(); fc_a = fc_nexta)
		{
			fc_nexta = fc_a->outchain;
			if (isconstraintarc(fc_a))
			{
				if (fc_a->to == fc_s)
					freearc(nfa, fc_a);
				else
					fc_hasconstraints = 1;
			}
		}
		/* 如果我们删除了所有出弧，该状态就是无用的。 */
		if (fc_s->nouts == 0 && !fc_s->flag)
			dropstate(nfa, fc_s);
	}

	/* 如果没有剩余的约束弧则无需操作 */
	if (NISERR() || !fc_hasconstraints)
		return;

	/*
	 * 从每个剩余的 NFA 状态开始，向外搜索约束环。如果找到环，则打破该环，然后重新开始搜索。（我们可以在第一次扫描中保留某些状态，但这样会大大复杂化，而且多状态约束环相对少见，因此不值得对该情况进行优化。）
	 */
restart:
	for (fc_s = nfa->states; fc_s != NULL && !NISERR(); fc_s = fc_s->next)
	{
		if (findconstraintloop(nfa, fc_s))
			goto restart;
	}

	if (NISERR())
		return;

	/*
	 * 现在移除任何变得无用的状态。（这次清理不是非常彻底，如果我们尝试将其与上一步结合起来将更不彻底；但 cleanup() 将处理我们遗漏的任何内容。）
	 *
	 * 因为 findconstraintloop 故意不重置所有 tmp 字段，我们必须在完成后清除它们。这也是一个方便的地方来做到这一点。
	 */
	for (fc_s = nfa->states; fc_s != NULL; fc_s = nexts)
	{
		nexts = fc_s->next;
		fc_s->tmp = NULL;
		if ((fc_s->nins == 0 || fc_s->nouts == 0) && !fc_s->flag)
			dropstate(nfa, fc_s);
	}

	if (fc_f != NULL)
		dumpnfa(nfa, fc_f);
}

/*
 * findconstraintloop - 递归查找约束弧的环
 *
 * 如果我们找到环，通过调用 breakconstraintloop() 来打破它，然后返回 1；否则返回 0。
 *
 * 状态 tmp 字段在成功返回时是保证为 NULL 的，因为 breakconstraintloop 会这样做。在失败返回后，任何被知道不属于环的状态都会标记为 s->tmp == s；这允许我们后续调用时不必重新证明这一事实。（这个约定是可行的，因为我们已经消除了单状态环。）
 *
 * 请注意，找到的环不一定包括我们第一次调用时的状态。任何从该状态可达的环都可以。
 *
 * 这里的最大递归深度比最长无环约束弧链的长度多 1，这肯定不超过 NFA 的大小……但这仍然可能引起问题。
 */
static int findconstraintloop(struct nfa *nfa, struct state *fc_s)
{
	struct arc *fc_a;

	/* 由于这是递归的，它可能导致堆栈溢出 */
	if (STACK_TOO_DEEP(nfa->v->re))
	{
		NERR(REG_ETOOBIG);
		return 1;				/* 以尽快退出 */
	}

	if (fc_s->tmp != NULL)
	{
		/* 已经证明无趣了吗？ */
		if (fc_s->tmp == fc_s)
			return 0;
		/* 找到一个涉及 s 的环 */
		breakconstraintloop(nfa, fc_s);
		/* tmp 字段已经被 breakconstraintloop 清理 */
		return 1;
	}
	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		if (isconstraintarc(fc_a))
		{
			struct state *fc_sto = fc_a->to;

			assert(fc_sto != fc_s);
			fc_s->tmp = fc_sto;
			if (findconstraintloop(nfa, fc_sto))
				return 1;
		}
	}

	/*
	 * 如果我们到这里，说明没有约束循环从 s 向外延伸。将其标记为
	 * s->tmp == s，这样我们以后就不需要重新发现这个事实。
	 */
	fc_s->tmp = fc_s;
	return 0;
}

/*
 * breakconstraintloop - 破坏约束弧的循环
 *
 * sinitial 是循环中的任一成员状态。每个循环成员的 tmp
 * 字段链接到其在循环中的后继。 （注意，此函数将重置所有 tmp 字段为 NULL。）
 *
 * 我们可以通过针对循环中的任一状态 S1，克隆其循环后继状态 S2 
 * （可能还有后续状态），然后将所有 S1->S2 约束弧移动到指向克隆的 S2 来打破循环。
 * 克隆的 S2 应该复制 S2 的任何非约束输出弧。如果约束输出弧指向 S1，则应丢弃它们，
 * 否则它们需要被复制为指向类似克隆状态 S3、S4 等的弧。通常，每个克隆状态复制
 * 非约束输出弧，丢弃可能导致自身或任何先前克隆状态的约束输出弧，并将其他约束输出
 * 弧发送到新克隆的状态。没有克隆状态会有不属于约束弧的输入弧，也不会来自 S1 或
 * 先前克隆状态。丢弃约束反向弧是可以的，因为它们不会将我们带到任何我们尚未到达的状态；
 * 因此，不会创建新的约束循环。通过这种方式，我们生成一个修改后的 NFA，它仍然可以代表
 * 每个有用的状态序列，但不包括那些表示没有消耗输入数据的状态循环的序列。请注意，
 * 克隆状态的集合肯定会包括除 S1 以外的所有循环成员状态，且它可能还包括通过约束
 * 弧可达的非循环状态。这一点很重要，因为没有保证 findconstraintloop 找到的是一个
 * 最大循环（而搜索一个将是 NP 难的，所以不尝试）。通常，“非循环状态”实际是我们
 * 未注意到的更大循环的一部分，确实可能存在多个重叠的循环。这种技术确保在这种情况下收敛，
 * 而仅考虑最初找到的循环则不这样做。
 *
 * 如果只有一个 S1->S2 约束弧，那么当我们进入任何克隆状态时，该约束肯定会得到满足。
 * 这意味着在许多约束弧标签相同的普通情况下，我们可以合并由相似标签的约束链接的克隆状态：
 * 如果我们可以到达第一个，那么我们肯定可以到达第二个，因此没有必要区分。这大大减少了
 * 所需的新状态数量，因此我们优先在这个是真的状态对处打破给定的循环。
 *
 * 此外，发现克隆的后继状态没有输出弧是相当常见的，特别是如果我们在删除不必要的
 * 输出弧时稍微激进一些。如果发生这种情况，则没有任何有趣的状态可以通过前驱的
 * 循环弧到达，这意味着我们可以通过删除这些循环弧来打破循环，且不添加新状态。
 */
static void breakconstraintloop(struct nfa *nfa, struct state *fc_sinitial)
{
	struct state *fc_s;
	struct state *fc_shead;
	struct state *fc_stail;
	struct state *fc_sclone;
	struct state *fc_nexts;
	struct arc *fc_refarc;
	struct arc *fc_a;
	struct arc *fc_nexta;

	/*
	 * 首先确定我们想要打破的循环步骤。
	 * 优先选择只有一个约束弧的步骤。 （XXX 我们是否想使用任何其他次要启发式？）
	 * 如果有，将 refarc 设置为指向所选的唯一约束弧。
	 */
	fc_refarc = NULL;
	fc_s = fc_sinitial;
	do
	{
		fc_nexts = fc_s->tmp;
		assert(fc_nexts != fc_s);		/* 不应看到任何单元素循环 */
		if (fc_refarc == NULL)
		{
			int			fc_narcs = 0;

			for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
			{
				if (fc_a->to == fc_nexts && isconstraintarc(fc_a))
				{
					fc_refarc = fc_a;
					fc_narcs++;
				}
			}
			assert(fc_narcs > 0);
			if (fc_narcs > 1)
				fc_refarc = NULL;	/* 这里有多个约束弧，不好 */
		}
		fc_s = fc_nexts;
	} while (fc_s != fc_sinitial);

	if (fc_refarc)
	{
		/* 在 refarc 处分割 */
		fc_shead = fc_refarc->from;
		fc_stail = fc_refarc->to;
		assert(fc_stail == fc_shead->tmp);
	}
	else
	{
		/* 为了没有更好的主意，在 sinitial 后进行分割 */
		fc_shead = fc_sinitial;
		fc_stail = fc_sinitial->tmp;
	}

	/*
	 * 重置 tmp 字段，以便我们可以在 clonesuccessorstates 中使用它们作为局部存储。
	 * （findconstraintloop 不会介意，因为它反正要放弃搜索。）
	 */
	for (fc_s = nfa->states; fc_s != NULL; fc_s = fc_s->next)
		fc_s->tmp = NULL;

	/*
	 * 根据需要递归构建克隆状态。
	 */
	fc_sclone = newstate(nfa);
	if (fc_sclone == NULL)
	{
		assert(NISERR());
		return;
	}

	clonesuccessorstates(nfa, fc_stail, fc_sclone, fc_shead, fc_refarc,
						 NULL, NULL, nfa->nstates);

	if (NISERR())
		return;

	/*
	 * sclone 可能根本没有输出弧，在这种情况下它是无用的。
	 * （我们不会非常努力地去除无用状态，但这是一个简单且相当常见的情况。）
	 */
	if (fc_sclone->nouts == 0)
	{
		freestate(nfa, fc_sclone);
		fc_sclone = NULL;
	}

	/*
	 * 将 shead 的约束循环弧移动指向 sclone，或者如果我们发现不需要 sclone，
	 * 则将其丢弃。
	 */
	for (fc_a = fc_shead->outs; fc_a != NULL; fc_a = fc_nexta)
	{
		fc_nexta = fc_a->outchain;
		if (fc_a->to == fc_stail && isconstraintarc(fc_a))
		{
			if (fc_sclone)
				cparc(nfa, fc_a, fc_shead, fc_sclone);
			freearc(nfa, fc_a);
			if (NISERR())
				break;
		}
	}
}


/*
 * clonesuccessorstates - 创建一个约束弧后继状态的树
 *
 * ssource 是要克隆的状态，sclone 是要复制其
 * 出弧的状态。sclone 的入弧（如果有的话）应该已经设置好。
 *
 * spredecessor 是我们试图为其构建后继的原始前驱状态
 * （它可能不是 ssource 的直接前驱）。refarc，如果不为 NULL，
 * 是已知已经从 spredecessor 遍历到后继状态的原始约束弧。
 *
 * 对于每个克隆的后继状态，我们暂时创建一个“donemap”，
 * 这是一个布尔数组，显示我们已经为这个克隆状态访问
 * 过哪些源状态。这可以防止无限递归以及对同一状态子树
 * 的无用重复访问（这可能很快累加，因为典型的 NFA
 * 有多个冗余的弧路径）。每个 donemap 是一个按状态号索引的
 * char 数组。所有 donemap 的大小相同“nstates”，
 * 这是在递归开始时 nfa->nstates 的值。这足以
 * 为所有已有状态添加条目，但 *不是* 为在递归期间创建的克隆
 * 状态添加条目。没关系，因为我们不需要标记那些。
 *
 * curdonemap 在递归到新的 sclone 状态时为 NULL，
 * 或者在我们没有创建新状态时（在我们决定
 * 可以将后继状态合并到当前克隆状态时所做的）为
 * sclone 的 donemap。outerdonemap 在顶层为 NULL，
 * 否则是父级克隆状态的 donemap。
 *
 * 我们在这里创建和填充的后继状态形成一个严格的树结构，
 * 每个状态都有一个前驱，除了顶层状态还没有入弧
 * （breakconstraintloop 以后会从 spredecessor 添加入弧）。
 * 因此，我们可以回溯检查 sclone 的入弧到根节点，
 * 加上 refarc（如果有的话），以识别当前点已经
 * 被认为有效的约束集合。这使我们能够避免生成额外的后继
 * 状态。
 */
static void clonesuccessorstates(struct nfa *nfa,
					 struct state *fc_ssource,
					 struct state *fc_sclone,
					 struct state *fc_spredecessor,
					 struct arc *fc_refarc,
					 char *fc_curdonemap,
					 char *fc_outerdonemap,
					 int fc_nstates)
{
	char	   *fc_donemap;
	struct arc *fc_a;

	/* 由于这是递归的，它可能导致堆栈溢出 */
	if (STACK_TOO_DEEP(nfa->v->re))
	{
		NERR(REG_ETOOBIG);
		return;
	}

	/* 如果这个状态还没有 donemap，创建一个 */
	fc_donemap = fc_curdonemap;
	if (fc_donemap == NULL)
	{
		fc_donemap = (char *) MALLOC(fc_nstates * sizeof(char));
		if (fc_donemap == NULL)
		{
			NERR(REG_ESPACE);
			return;
		}

		if (fc_outerdonemap != NULL)
		{
			/*
			 * 不是在最外层的递归级别，所以复制外层的
			 * donemap；这确保我们在外层访问的过程中
			 * 可以看到正在处理的状态，或已合并到前驱
			 * 状态的状态，作为我们不应返回的状态。
			 */
			memcpy(fc_donemap, fc_outerdonemap, fc_nstates * sizeof(char));
		}
		else
		{
			/* 在最外层级别，只有 spredecessor 是禁止的 */
			memset(fc_donemap, 0, fc_nstates * sizeof(char));
			assert(fc_spredecessor->no < fc_nstates);
			fc_donemap[fc_spredecessor->no] = 1;
		}
	}

	/* 在 donemap 中标记 ssource 为已访问 */
	assert(fc_ssource->no < fc_nstates);
	assert(fc_donemap[fc_ssource->no] == 0);
	fc_donemap[fc_ssource->no] = 1;

	/*
	 * 我们首先克隆 ssource 的所有出弧，按需创建新的
	 * 克隆状态，但不对此做更多的处理。然后在第二次
	 * 递归中，处理子克隆状态。这使我们能够对每个可达源
	 * 状态仅有一个子克隆状态，即使有多个出弧通向同一状态。
	 * 此外，当我们访问子状态时，其入弧的集合已被确切知晓，
	 * 这使得应用约束已被检查的优化是安全的。同时，这确保我们
	 * 在递归到任何子状态之前，已经将所有可以合并的状态
	 * 合并到当前克隆中，从而可能避免它们多次生成这些状态的
	 * 额外图像。
	 *
	 * 当这个函数运行时，当前状态的子克隆状态通过设置
	 * 它们的 tmp 字段指向原始状态来标记。这使检测多个出弧
	 * 通向同一状态成为可能，也使区分克隆状态与原始状态
	 * 变得容易（原始状态的 tmp 将为 NULL）。
	 */
	for (fc_a = fc_ssource->outs; fc_a != NULL && !NISERR(); fc_a = fc_a->outchain)
	{
		struct state *fc_sto = fc_a->to;

		/*
		 * 我们不考虑克隆没有约束出弧的后继状态；
		 * 只需按原样链接到它们。它们不可能是约束循环的一部分，
		 * 所以没有必要复制。特别是，这条规则阻止我们尝试克隆
		 * 后状态，这将是个糟糕的主意。
		 */
		if (isconstraintarc(fc_a) && hasconstraintout(fc_sto))
		{
			struct state *fc_prevclone;
			int			fc_canmerge;
			struct arc *fc_a2;

			/*
			 * 不得跟随反向链约束弧。也没有必要重新访问先前合并到
			 * 这个克隆中的状态。
			 */
			assert(fc_sto->no < fc_nstates);
			if (fc_donemap[fc_sto->no] != 0)
				continue;

			/*
			 * 检查我们是否已经有这个源状态的子克隆状态。
			 */
			fc_prevclone = NULL;
			for (fc_a2 = fc_sclone->outs; fc_a2 != NULL; fc_a2 = fc_a2->outchain)
			{
				if (fc_a2->to->tmp == fc_sto)
				{
					fc_prevclone = fc_a2->to;
					break;
				}
			}

			/*
			 * 如果这个弧的标签与 refarc 相同，或者与我们必须
			 * 遍历以到达 sclone 的任何弧相同，那么到达 sto
			 * 不需要满足额外的约束，因此我们应该只将它的出弧
			 * 合并到 sclone 中。
			 */
			if (fc_refarc && fc_a->type == fc_refarc->type && fc_a->co == fc_refarc->co)
				fc_canmerge = 1;
			else
			{
				struct state *fc_s;

				fc_canmerge = 0;
				for (fc_s = fc_sclone; fc_s->ins; fc_s = fc_s->ins->from)
				{
					if (fc_s->nins == 1 &&
						fc_a->type == fc_s->ins->type && fc_a->co == fc_s->ins->co)
					{
						fc_canmerge = 1;
						break;
					}
				}
			}

			if (fc_canmerge)
			{
				/*
				 * 我们可以合并到 sclone 中。如果我们之前创建了一个
				 * 子克隆状态，则丢弃它；没有必要访问它。
				 * （如果 ssource 有多条通路到 sto，我们刚刚发现
				 * 一条证明为无操作的通路时，这可能会发生。）
				 */
				if (fc_prevclone)
					dropstate(nfa, fc_prevclone);	/* 也会导致我们的出弧被删除 */

				/* 递归以将 sto 的出弧合并到 sclone 中 */
				clonesuccessorstates(nfa,
									 fc_sto,
									 fc_sclone,
									 fc_spredecessor,
									 fc_refarc,
									 fc_donemap,
									 fc_outerdonemap,
									 fc_nstates);
				/* sto 现在应该被标记为之前访问过 */
				assert(NISERR() || fc_donemap[fc_sto->no] == 1);
			}
			else if (fc_prevclone)
			{
				
/*
				 * 我们已经有了这个后继的克隆状态，所以只需
				 * 再给它加一个弧。
				 */
				cparc(nfa, fc_a, fc_sclone, fc_prevclone);
			}
			else
			{
				/*
				 * 我们需要创建一个新的后继克隆状态。
				 */
				struct state *fc_stoclone;

				fc_stoclone = newstate(nfa);
				if (fc_stoclone == NULL)
				{
					assert(NISERR());
					break;
				}
				/* 标记它是克隆的什么 */
				fc_stoclone->tmp = fc_sto;
				/* ... 并添加通向它的 outarc */
				cparc(nfa, fc_a, fc_sclone, fc_stoclone);
			}
		}
		else
		{
			/*
			 * 非约束 outarcs 只是被复制到 sclone，通向没有约束 outarc 的状态的 outarcs 也是如此。
			 */
			cparc(nfa, fc_a, fc_sclone, fc_sto);
		}
	}

	/*
	 * 如果我们处于该克隆状态的外层级别，则递归到它所有的子克隆状态，同时清除它们的 tmp 字段。 
	 * （如果我们不是 sclone 的最外层，则将此留给外部调用级别来完成。） 
	 * 请注意，如果我们有多个 outarcs 通向相同的克隆状态，则只会递归一次。
	 */
	if (fc_curdonemap == NULL)
	{
		for (fc_a = fc_sclone->outs; fc_a != NULL && !NISERR(); fc_a = fc_a->outchain)
		{
			struct state *fc_stoclone = fc_a->to;
			struct state *fc_sto = fc_stoclone->tmp;

			if (fc_sto != NULL)
			{
				fc_stoclone->tmp = NULL;
				clonesuccessorstates(nfa,
									 fc_sto,
									 fc_stoclone,
									 fc_spredecessor,
									 fc_refarc,
									 NULL,
									 fc_donemap,
									 fc_nstates);
			}
		}

		/* 完成后不要忘了释放 sclone 的 donemap */
		FREE(fc_donemap);
	}
}

/*
 * removecantmatch - 移除 CANTMATCH arcs，这在解析阶段完成后就不再有用。
 * （我们只在解析过程中需要它们，以保持 NFA 子图的连通性。）
 */
static void removecantmatch(struct nfa *nfa)
{
	struct state *fc_s;

	for (fc_s = nfa->states; fc_s != NULL; fc_s = fc_s->next)
	{
		struct arc *fc_a;
		struct arc *fc_nexta;

		for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_nexta)
		{
			fc_nexta = fc_a->outchain;
			if (fc_a->type == CANTMATCH)
			{
				freearc(nfa, fc_a);
				if (NISERR())
					return;
			}
		}
	}
}

/*
 * cleanup - 优化后的 NFA 清理
 */
static void cleanup(struct nfa *nfa)
{
	struct state *fc_s;
	struct state *fc_nexts;
	int			fc_n;

	if (NISERR())
		return;

	/* 清除不可达或死胡同状态 */
	/* 使用 pre 标记可达，然后使用 post 标记可达 post */
	markreachable(nfa, nfa->pre, (struct state *) NULL, nfa->pre);
	markcanreach(nfa, nfa->post, nfa->pre, nfa->post);
	for (fc_s = nfa->states; fc_s != NULL && !NISERR(); fc_s = fc_nexts)
	{
		fc_nexts = fc_s->next;
		if (fc_s->tmp != nfa->post && !fc_s->flag)
			dropstate(nfa, fc_s);
	}
	assert(NISERR() || nfa->post->nins == 0 || nfa->post->tmp == nfa->post);
	cleartraverse(nfa, nfa->pre);
	assert(NISERR() || nfa->post->nins == 0 || nfa->post->tmp == NULL);
	/* nins==0（最终不可达）情况稍后会被捕获 */

	/* 重新编号幸存状态 */
	fc_n = 0;
	for (fc_s = nfa->states; fc_s != NULL; fc_s = fc_s->next)
		fc_s->no = fc_n++;
	nfa->nstates = fc_n;
}

/*
 * markreachable - 递归标记可达状态
 */
static void markreachable(struct nfa *nfa,
			  struct state *fc_s,
			  struct state *fc_okay,	/* 仅考虑具有此标记的状态 */
			  struct state *fc_mark)	/* 要标记的值 */
{
	struct arc *fc_a;

	/* 由于这是递归的，它可能导致堆栈溢出 */
	if (STACK_TOO_DEEP(nfa->v->re))
	{
		NERR(REG_ETOOBIG);
		return;
	}

	if (fc_s->tmp != fc_okay)
		return;
	fc_s->tmp = fc_mark;

	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
		markreachable(nfa, fc_a->to, fc_okay, fc_mark);
}

/*
 * markcanreach - 递归标记可以到达此处的状态
 */
static void markcanreach(struct nfa *nfa,
			 struct state *fc_s,
			 struct state *fc_okay,	/* 仅考虑具有此标记的状态 */
			 struct state *fc_mark)	/* 要标记的值 */
{
	struct arc *fc_a;

	/* 由于这是递归的，它可能导致堆栈溢出 */
	if (STACK_TOO_DEEP(nfa->v->re))
	{
		NERR(REG_ETOOBIG);
		return;
	}

	if (fc_s->tmp != fc_okay)
		return;
	fc_s->tmp = fc_mark;

	for (fc_a = fc_s->ins; fc_a != NULL; fc_a = fc_a->inchain)
		markcanreach(nfa, fc_a->from, fc_okay, fc_mark);
}

/*
 * analyze - 确定关于优化 NFA 的潜在有用事实
 */
static long						/* 要进行 OR 处理的 re_info 位 */
analyze(struct nfa *nfa)
{
	struct arc *fc_a;
	struct arc *fc_aa;

	if (NISERR())
		return 0;

	/* 检测 NFA 是否无法匹配任何内容 */
	if (nfa->pre->outs == NULL)
		return REG_UIMPOSSIBLE;

	/* 检测 NFA 是否匹配所有字符串（可能有长度限制） */
	checkmatchall(nfa);

	/* 检测 NFA 是否可能匹配零长度字符串 */
	for (fc_a = nfa->pre->outs; fc_a != NULL; fc_a = fc_a->outchain)
		for (fc_aa = fc_a->to->outs; fc_aa != NULL; fc_aa = fc_aa->outchain)
			if (fc_aa->to == nfa->post)
				return REG_UEMPTYMATCH;
	return 0;
}

/*
 * checkmatchall - NFA 是否仅代表字符串长度测试？
 *
 * 如果是，则正确设置 nfa->minmatchall 和 nfa->maxmatchall （它们起初是 -1），并在 nfa->flags 中设置 MATCHALL 位。
 *
 * 要成功，我们要求所有 arcs 都是 PLAIN RAINBOW arcs，除了伪颜色的那些（即 BOS/BOL/EOS/EOL）。
 * 我们必须能够通过 RAINBOW arcs 到达后状态，如果图中有任何循环，它们
 * 必须是自循环 arcs，确保每次循环迭代消耗
 * 正好一个字符。 （较长的循环是有问题的，因为它们创建
 * 非连续的可能匹配长度；我们没有好的方法来表示
 * 超出 DUPINF 限制的长度情况。）
 *
 * 伪颜色 arcs 使事情复杂了一些。 我们知道它们只能
 * 作为 pre 状态的 outarcs（对于 BOS/BOL）或后状态的 inarcs（对于
 * EOS/EOL）出现。 在那里，它们必须完全复制并行的 RAINBOW arcs，
 * 例如，如果 pre 状态有一个 RAINBOW outarc 到状态 2，它必须有 BOS
 * 和 BOL outarcs 到状态 2，没有其他。 缺失或额外的伪颜色
 * arcs 可能会出现，这意味着 NFA 涉及对相邻字符的一些约束，这使其不是一个 matchall NFA。
 */
static void checkmatchall(struct nfa *nfa)
{
	bool	  **fc_haspaths;
	struct state *fc_s;
	int			fc_i;

	/*
	 * 如果状态太多，就不要费心尝试检测 matchall。
	 * 此限制用于界定我们可能消耗的时间和内存。
	 * 请注意，即使图是全 RAINBOW，如果状态数明显超过
	 * DUPINF，那么很可能存在长度超过 DUPINF 的路径，这将强迫我们无论如何失败。
	 * 实际上，写一个具有最大有限路径
	 * 长度 K 的 matchall 正则表达式的合理方式通常不会有比 K 状态多得多。
	 */
	if (nfa->nstates > DUPINF * 2)
		return;

	/*
	 * 首先，扫描所有状态以验证只有 RAINBOW arcs 出现，
	 * 以及与 pre 和 post 状态相邻的伪颜色 arcs。 
	 * 这让我们迅速消除大多数不是 matchall NFA 的情况。
	 */
	for (fc_s = nfa->states; fc_s != NULL; fc_s = fc_s->next)
	{
		struct arc *fc_a;

		for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
		{
			if (fc_a->type != PLAIN)
				return;			/* 任何 LACON 使其不成为 matchall */
			if (fc_a->co != RAINBOW)
			{
				if (nfa->cm->cd[fc_a->co].flags & PSEUDO)
				{
					/*
					 * 伪颜色 arc：验证它在有效的位置 
					 * （这看起来很不可能失败，但我们还是要确认）。 
					 */
					if (fc_s == nfa->pre &&
						(fc_a->co == nfa->bos[0] || fc_a->co == nfa->bos[1]))
						 /* 好的 BOS/BOL arc */ ;
					else if (fc_a->to == nfa->post &&
							 (fc_a->co == nfa->eos[0] || fc_a->co == nfa->eos[1]))
						 /* 好的 EOS/EOL arc */ ;
					else
						return; /* 意外的伪颜色 arc */
					/* 我们将在下面进一步检查这些 arcs。 */
				}
				else
					return;		/* 其他任何颜色都使其不具匹配所有的特性 */
			}
		}
		/* 另外，断言 tmp 字段可用于使用。 */
		assert(fc_s->tmp == NULL);
	}

	/* 
	 * 我们可以进行的下一个最便宜的检查是验证前状态的 BOS/BOL 
	 * 外部弧是否到达与其 RAINBOW 外部弧相同的状态。
	 * 如果不一致，NFA 就会对匹配的字符串之前的字符施加一些限制， 
	 * 使其变得不匹配所有情况。 同样，后状态的 EOS/EOL 
	 * 内部弧必须与其 RAINBOW 内部弧匹配。
	 */
	if (!check_out_colors_match(nfa->pre, RAINBOW, nfa->bos[0]) ||
		!check_out_colors_match(nfa->pre, RAINBOW, nfa->bos[1]) ||
		!check_in_colors_match(nfa->post, RAINBOW, nfa->eos[0]) ||
		!check_in_colors_match(nfa->post, RAINBOW, nfa->eos[1]))
		return;

	/* 
	 * 初始化一个路径长度数组，该数组中 
	 * checkmatchall_recurse 将返回每个状态的结果。 这让我们 
	 * 可以对递归搜索进行备忘，避免指数时间消耗。
	 */
	fc_haspaths = (bool **) MALLOC(nfa->nstates * sizeof(bool *));
	if (fc_haspaths == NULL)
		return;					/* 安静失败 */
	memset(fc_haspaths, 0, nfa->nstates * sizeof(bool *));

	/* 
	 * 递归搜索图中到“后”状态的所有 RAINBOW 路径，从“前”状态开始，并计算路径的长度。
	 * （根据前面的检查，应该至少有一条这样的路径。
	 * 但是，如果存在多状态循环、超出 DUPINF+1 的路径长度，或者诸如 ENOMEM 
	 * 等非算法故障，我们仍然可能会返回错误结果。）
	 */
	if (checkmatchall_recurse(nfa, nfa->pre, fc_haspaths))
	{
		/* 有用的结果是前状态的路径长度数组 */
		bool	   *fc_haspath = fc_haspaths[nfa->pre->no];
		int			fc_minmatch,
					fc_maxmatch,
					fc_morematch;

		assert(fc_haspath != NULL);

		/* 
		 * haspath[] 现在表示可能路径长度的集合；但我们 
		 * 想要将其减少到最小和最大值，因为将 regexec.c 
		 * 复杂化以处理不连续的可能匹配长度似乎没有意义。
		 * 找到第一轮长度的最小和最大值，然后 
		 * 验证没有不连续的长度。
		 */
		for (fc_minmatch = 0; fc_minmatch <= DUPINF + 1; fc_minmatch++)
		{
			if (fc_haspath[fc_minmatch])
				break;
		}
		assert(fc_minmatch <= DUPINF + 1); /* 否则 checkmatchall_recurse 就是撒谎 */
		for (fc_maxmatch = fc_minmatch; fc_maxmatch < DUPINF + 1; fc_maxmatch++)
		{
			if (!fc_haspath[fc_maxmatch + 1])
				break;
		}
		for (fc_morematch = fc_maxmatch + 1; fc_morematch <= DUPINF + 1; fc_morematch++)
		{
			if (fc_haspath[fc_morematch])
			{
				fc_haspath = NULL; /* 失败，存在不连续的长度 */
				break;
			}
		}

		if (fc_haspath != NULL)
		{
			/* 
			 * 成功，因此记录信息。 这里我们有一个细微的点：从前状态 
			 * 到后状态的路径长度包括前到初始的转换，因此 
			 * 它比实际匹配的字符串长度多一个。 （我们避免在 
			 * checkmatchall_recurse 中计算最终到后状态的转换，
			 * 但不包括这个。）这就是为什么 
			 * checkmatchall_recurse 允许比看起来必要的路径长度多出一个级别。
			 * 这个递减也解决了将 checkmatchall_recurse 的“无穷大” 
			 * 定义（作为“DUPINF+1”）转换为我们正常的表示（作为“DUPINF”）的问题。
			 */
			assert(fc_minmatch > 0);	/* 否则前后状态是相邻的 */
			nfa->minmatchall = fc_minmatch - 1;
			nfa->maxmatchall = fc_maxmatch - 1;
			nfa->flags |= MATCHALL;
		}
	}

	/* 清理 */
	for (fc_i = 0; fc_i < nfa->nstates; fc_i++)
	{
		if (fc_haspaths[fc_i] != NULL)
			FREE(fc_haspaths[fc_i]);
	}
	FREE(fc_haspaths);
}

/* 
 * checkmatchall_recurse - 递归搜索 checkmatchall
 *
 * s 是本次递归级别中要检查的状态。
 * haspaths[] 是每个状态退出路径长度数组。
 *
 * 如果搜索成功执行则返回 true，若因为多状态循环或其他内部原因失败则返回 false。
 * （因为已经消除了无法达到后状态的“死”状态，并且我们已经验证了仅存在 RAINBOW 和匹配的
 * 伪色弧，因此每个状态都应该有一条到后状态的 RAINBOW 路径。
 * 因此，我们从递归调用中获取到的错误结果意味着我们最好完全失败，而不仅仅是该特定状态无法到达后状态。）
 *
 * 在成功时，我们在 haspaths[s->no] 中存储一个通过 malloc 分配的结果数组，
 * 显示从 s 到后状态的可能路径长度。
 * 每个状态的 haspath[] 数组长度为 DUPINF+2。从 k = 0 到 DUPINF 的条目
 * 如果存在从该状态到字符串结尾的全 RAINBOW 路径则为 true。
 * 如果所有路径长度 >= DUPINF+1 都是可能的，则 haspath[DUPINF+1] 为 true。
 * （无法在这些规则下表示的情况会导致失败。）
 *
 * checkmatchall 负责最终释放 haspath[] 数组。
 */
static bool checkmatchall_recurse(struct nfa *nfa, struct state *fc_s, bool **fc_haspaths)
{
	bool		fc_result = false;
	bool		fc_foundloop = false;
	bool	   *fc_haspath;
	struct arc *fc_a;

	/* 
	 * 由于这是递归的，可能会导致栈溢出。但是我们不 
	 * 需要将其视为硬性失败；只是认为 NFA 不匹配所有情况。
	 */
	if (STACK_TOO_DEEP(nfa->v->re))
		return false;

	/* 以防搜索时间过长，检查是否取消 */
	if (CANCEL_REQUESTED(nfa->v->re))
	{
		NERR(REG_CANCEL);
		return false;
	}

	/* 为这个状态创建一个 haspath 数组 */
	fc_haspath = (bool *) MALLOC((DUPINF + 2) * sizeof(bool));
	if (fc_haspath == NULL)
		return false;			/* 再次，将其视为不匹配所有情况 */
	memset(fc_haspath, 0, (DUPINF + 2) * sizeof(bool));

	/* 标记该状态为已访问 */
	assert(fc_s->tmp == NULL);
	fc_s->tmp = fc_s;

	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		if (fc_a->co != RAINBOW)
			continue;			/* 忽略伪色弧 */
		if (fc_a->to == nfa->post)
		{
			/* 我们找到了到后状态的全 RAINBOW 路径 */
			fc_result = true;

			/* 
			 * 将该状态标记为距离字符串结尾零步
			 * （到后状态的转换不算在内）。
			 */
			fc_haspath[0] = true;
		}
		else if (fc_a->to == fc_s)
		{
			/* 我们找到了长度为 1 的循环，将在下面处理。 */
			fc_foundloop = true;
		}
		else if (fc_a->to->tmp != NULL)
		{
			/* 它是忙碌的，所以我们找到一个长度 > 1 的循环，因此失败。 */
			fc_result = false;
			break;
		}
		else
		{
			/* 考虑通过这个到状态的前进路径。 */
			bool	   *fc_nexthaspath;
			int			fc_i;

			/* 如果到状态尚未访问过，则递归 */
			if (fc_haspaths[fc_a->to->no] == NULL)
			{
				fc_result = checkmatchall_recurse(nfa, fc_a->to, fc_haspaths);
				/* 如果任何递归路径失败则失败 */
				if (!fc_result)
					break;
			}
			else
			{
				/* 先前的访问必须已找到到结束的路径 */
				fc_result = true;
			}
			assert(fc_a->to->tmp == NULL);
			fc_nexthaspath = fc_haspaths[fc_a->to->no];
			assert(fc_nexthaspath != NULL);

			/* 
			 * 现在，对于从 a->to 到字符串结尾的每条长度为 i 的路径， 
			 * 从 s 到字符串结尾的路径长度为 i + 1。
			 */
			if (fc_nexthaspath[DUPINF] != fc_nexthaspath[DUPINF + 1])
			{
				
/*
				 * a->to 具有长度恰好为 DUPINF 的路径，但没有更长的路径；
				 * 或者它具有所有长度 > DUPINF 的路径，但没有长度恰好为
				 * DUPINF 的路径。在这两种情况下，我们无法正确表示
				 * 从 s 出发的可能路径长度，因此失败。
				 */
				fc_result = false;
				break;
			}
			/* 将这些路径长度的知识合并到我们所拥有的内容中 */
			for (fc_i = 0; fc_i < DUPINF; fc_i++)
				fc_haspath[fc_i + 1] |= fc_nexthaspath[fc_i];
			/* 无穷大 + 1 仍然是无穷大 */
			fc_haspath[DUPINF + 1] |= fc_nexthaspath[DUPINF + 1];
		}
	}

	if (fc_result && fc_foundloop)
	{
		/*
		 * 如果在此状态下存在长度为1的环，则找到已知的最短路径长度到达终点。环意味着任何更大路径长度也是可能的。（无论任何较长的长度是否已知为可能并不重要。）
		 */
		int			fc_i;

		for (fc_i = 0; fc_i <= DUPINF; fc_i++)
		{
			if (fc_haspath[fc_i])
				break;
		}
		for (fc_i++; fc_i <= DUPINF + 1; fc_i++)
			fc_haspath[fc_i] = true;
	}

	/* 报告已完成的路径长度图 */
	assert(fc_s->no < nfa->nstates);
	assert(fc_haspaths[fc_s->no] == NULL);
	fc_haspaths[fc_s->no] = fc_haspath;

	/* 标记状态不再忙碌 */
	fc_s->tmp = NULL;

	return fc_result;
}

/*
 * check_out_colors_match - checkmatchall 的子程序
 *
 * 检查从状态 s 通过颜色 co1 的弧可到达的状态集合是否等同于通过颜色 co2 的弧可到达的状态集合。
 * checkmatchall 已经验证了所有 NFA 的弧都是简单的，
 * 因此我们无需在此检查弧类型。
 */
static bool check_out_colors_match(struct state *fc_s, color fc_co1, color fc_co2)
{
	bool		fc_result = true;
	struct arc *fc_a;

	/*
	 * 为了以线性时间完成此操作，我们假设 NFA 不包含重复的
	 * 弧。遍历输出弧，标记通过颜色 co1 的弧可到达的状态。再遍历一次，取消标记通过颜色 co2 的弧可到达的状态；如果看到未标记的状态，我们知道这个 co2 弧是
	 * 不匹配的。然后再遍历一次，检查仍然被标记的状态，
	 * 无论如何都将所有 tmp 字段重置为 NULL。
	 */
	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		if (fc_a->co == fc_co1)
		{
			assert(fc_a->to->tmp == NULL);
			fc_a->to->tmp = fc_a->to;
		}
	}
	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		if (fc_a->co == fc_co2)
		{
			if (fc_a->to->tmp != NULL)
				fc_a->to->tmp = NULL;
			else
				fc_result = false; /* 不匹配的 co2 弧 */
		}
	}
	for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		if (fc_a->co == fc_co1)
		{
			if (fc_a->to->tmp != NULL)
			{
				fc_result = false; /* 不匹配的 co1 弧 */
				fc_a->to->tmp = NULL;
			}
		}
	}
	return fc_result;
}

/*
 * check_in_colors_match - checkmatchall 的子程序
 *
 * 检查可以通过颜色 co1 的弧到达状态 s 的状态集合是否等同于可以通过颜色 co2 的弧到达状态 s 的状态集合。
 * checkmatchall 已经验证了所有 NFA 的弧都是简单的，
 * 因此我们无需在此检查弧类型。
 */
static bool check_in_colors_match(struct state *fc_s, color fc_co1, color fc_co2)
{
	bool		fc_result = true;
	struct arc *fc_a;

	/*
	 * 与 check_out_colors_match 相同的算法，只是检查状态 s' 的输入弧的起始状态。
	 */
	for (fc_a = fc_s->ins; fc_a != NULL; fc_a = fc_a->inchain)
	{
		if (fc_a->co == fc_co1)
		{
			assert(fc_a->from->tmp == NULL);
			fc_a->from->tmp = fc_a->from;
		}
	}
	for (fc_a = fc_s->ins; fc_a != NULL; fc_a = fc_a->inchain)
	{
		if (fc_a->co == fc_co2)
		{
			if (fc_a->from->tmp != NULL)
				fc_a->from->tmp = NULL;
			else
				fc_result = false; /* 不匹配的 co2 弧 */
		}
	}
	for (fc_a = fc_s->ins; fc_a != NULL; fc_a = fc_a->inchain)
	{
		if (fc_a->co == fc_co1)
		{
			if (fc_a->from->tmp != NULL)
			{
				fc_result = false; /* 不匹配的 co1 弧 */
				fc_a->from->tmp = NULL;
			}
		}
	}
	return fc_result;
}

/*
 * compact - 构建 NFA 的紧凑表示
 */
static void compact(struct nfa *nfa,
		struct cnfa *fc_cnfa)
{
	struct state *fc_s;
	struct arc *fc_a;
	size_t		fc_nstates;
	size_t		fc_narcs;
	struct carc *fc_ca;
	struct carc *fc_first;

	assert(!NISERR());

	fc_nstates = 0;
	fc_narcs = 0;
	for (fc_s = nfa->states; fc_s != NULL; fc_s = fc_s->next)
	{
		fc_nstates++;
		fc_narcs += fc_s->nouts + 1;	/* 需要一个额外的结束标记 */
	}

	fc_cnfa->stflags = (char *) MALLOC(fc_nstates * sizeof(char));
	fc_cnfa->states = (struct carc **) MALLOC(fc_nstates * sizeof(struct carc *));
	fc_cnfa->arcs = (struct carc *) MALLOC(fc_narcs * sizeof(struct carc));
	if (fc_cnfa->stflags == NULL || fc_cnfa->states == NULL || fc_cnfa->arcs == NULL)
	{
		if (fc_cnfa->stflags != NULL)
			FREE(fc_cnfa->stflags);
		if (fc_cnfa->states != NULL)
			FREE(fc_cnfa->states);
		if (fc_cnfa->arcs != NULL)
			FREE(fc_cnfa->arcs);
		NERR(REG_ESPACE);
		return;
	}
	fc_cnfa->nstates = fc_nstates;
	fc_cnfa->pre = nfa->pre->no;
	fc_cnfa->post = nfa->post->no;
	fc_cnfa->bos[0] = nfa->bos[0];
	fc_cnfa->bos[1] = nfa->bos[1];
	fc_cnfa->eos[0] = nfa->eos[0];
	fc_cnfa->eos[1] = nfa->eos[1];
	fc_cnfa->ncolors = maxcolor(nfa->cm) + 1;
	fc_cnfa->flags = nfa->flags;
	fc_cnfa->minmatchall = nfa->minmatchall;
	fc_cnfa->maxmatchall = nfa->maxmatchall;

	fc_ca = fc_cnfa->arcs;
	for (fc_s = nfa->states; fc_s != NULL; fc_s = fc_s->next)
	{
		assert((size_t) fc_s->no < fc_nstates);
		fc_cnfa->stflags[fc_s->no] = 0;
		fc_cnfa->states[fc_s->no] = fc_ca;
		fc_first = fc_ca;
		for (fc_a = fc_s->outs; fc_a != NULL; fc_a = fc_a->outchain)
			switch (fc_a->type)
			{
				case PLAIN:
					fc_ca->co = fc_a->co;
					fc_ca->to = fc_a->to->no;
					fc_ca++;
					break;
				case LACON:
					assert(fc_s->no != fc_cnfa->pre);
					assert(fc_a->co >= 0);
					fc_ca->co = (color) (fc_cnfa->ncolors + fc_a->co);
					fc_ca->to = fc_a->to->no;
					fc_ca++;
					fc_cnfa->flags |= HASLACONS;
					break;
				default:
					NERR(REG_ASSERT);
					return;
			}
		carcsort(fc_first, fc_ca - fc_first);
		fc_ca->co = COLORLESS;
		fc_ca->to = 0;
		fc_ca++;
	}
	assert(fc_ca == &fc_cnfa->arcs[fc_narcs]);
	assert(fc_cnfa->nstates != 0);

	/* 标记未进展的状态 */
	for (fc_a = nfa->pre->outs; fc_a != NULL; fc_a = fc_a->outchain)
		fc_cnfa->stflags[fc_a->to->no] = CNFA_NOPROGRESS;
	fc_cnfa->stflags[nfa->pre->no] = CNFA_NOPROGRESS;
}

/*
 * carcsort - 按颜色对紧凑 NFA 的弧进行排序
 */
static void carcsort(struct carc *fc_first, size_t fc_n)
{
	if (fc_n > 1)
		qsort(fc_first, fc_n, sizeof(struct carc), carc_cmp);
}

static int carc_cmp(const void *fc_a, const void *fc_b)
{
	const struct carc *fc_aa = (const struct carc *) fc_a;
	const struct carc *fc_bb = (const struct carc *) fc_b;

	if (fc_aa->co < fc_bb->co)
		return -1;
	if (fc_aa->co > fc_bb->co)
		return +1;
	if (fc_aa->to < fc_bb->to)
		return -1;
	if (fc_aa->to > fc_bb->to)
		return +1;
	/* 这是未被到达的，因为现在不应该有重复的弧： */
	return 0;
}

/*
 * freecnfa - 释放紧凑 NFA
 */
static void freecnfa(struct cnfa *cnfa)
{
	assert(!NULLCNFA(*cnfa));	/* 不再为空 */
	FREE(cnfa->stflags);
	FREE(cnfa->states);
	FREE(cnfa->arcs);
	ZAPCNFA(*cnfa);
}

/*
 * dumpnfa - 以人类可读的形式转储 NFA
 */
static void dumpnfa(struct nfa *nfa,
		FILE *fc_f)
{
#ifdef REG_DEBUG
	struct state *fc_s;
	int			fc_nstates = 0;
	int			fc_narcs = 0;

	fprintf(fc_f, "pre %d, post %d", nfa->pre->no, nfa->post->no);
	if (nfa->bos[0] != COLORLESS)
		fprintf(fc_f, ", bos [%ld]", (long) nfa->bos[0]);
	if (nfa->bos[1] != COLORLESS)
		fprintf(fc_f, ", bol [%ld]", (long) nfa->bos[1]);
	if (nfa->eos[0] != COLORLESS)
		fprintf(fc_f, ", eos [%ld]", (long) nfa->eos[0]);
	if (nfa->eos[1] != COLORLESS)
		fprintf(fc_f, ", eol [%ld]", (long) nfa->eos[1]);
	if (nfa->flags & HASLACONS)
		fprintf(fc_f, ", haslacons");
	if (nfa->flags & HASCANTMATCH)
		fprintf(fc_f, ", hascantmatch");
	if (nfa->flags & MATCHALL)
	{
		fprintf(fc_f, ", minmatchall %d", nfa->minmatchall);
		if (nfa->maxmatchall == DUPINF)
			fprintf(fc_f, ", maxmatchall inf");
		else
			fprintf(fc_f, ", maxmatchall %d", nfa->maxmatchall);
	}
	fprintf(fc_f, "\n");
	for (fc_s = nfa->states; fc_s != NULL; fc_s = fc_s->next)
	{
		dumpstate(fc_s, fc_f);
		fc_nstates++;
		fc_narcs += fc_s->nouts;
	}
	fprintf(fc_f, "total of %d states, %d arcs\n", fc_nstates, fc_narcs);
	if (nfa->parent == NULL)
		dumpcolors(nfa->cm, fc_f);
	fflush(fc_f);
#endif
}

#ifdef REG_DEBUG				/* dumpnfa 的下属 */

/*
 * dumpstate - 以人类可读的形式转储 NFA 状态
 */
static void dumpstate(struct state *fc_s,
		  FILE *fc_f)
{
	struct arc *fc_a;

	fprintf(fc_f, "%d%s%c", fc_s->no, (fc_s->tmp != NULL) ? "T" : "",
			(fc_s->flag) ? fc_s->flag : '.');
	if (fc_s->prev != NULL && fc_s->prev->next != fc_s)
		fprintf(fc_f, "\tstate chain bad\n");
	if (fc_s->nouts == 0)
		fprintf(fc_f, "\tno out arcs\n");
	else
		dumparcs(fc_s, fc_f);
	for (fc_a = fc_s->ins; fc_a != NULL; fc_a = fc_a->inchain)
	{
		if (fc_a->to != fc_s)
			fprintf(fc_f, "\tlink from %d to %d on %d's in-chain\n",
					fc_a->from->no, fc_a->to->no, fc_s->no);
	}
	fflush(fc_f);
}

/*
 * dumparcs - 以人类可读的形式转储输出弧
 */
static void dumparcs(struct state *fc_s,
		 FILE *fc_f)
{
	int			fc_pos;
	struct arc *fc_a;

	/* 首先打印最旧的弧通常更清晰 */
	fc_a = fc_s->outs;
	assert(fc_a != NULL);
	while (fc_a->outchain != NULL)
		fc_a = fc_a->outchain;
	fc_pos = 1;
	do
	{
		dumparc(fc_a, fc_s, fc_f);
		if (fc_pos == 5)
		{
			fprintf(fc_f, "\n");
			fc_pos = 1;
		}
		else
			fc_pos++;
		fc_a = fc_a->outchainRev;
	} while (fc_a != NULL);
	if (fc_pos != 1)
		fprintf(fc_f, "\n");
}

/*
 * dumparc - 以可读形式转储一个输出弧，包括前缀制表符
 */
static void dumparc(struct arc *fc_a,
		struct state *fc_s,
		FILE *fc_f)
{
	struct arc *fc_aa;

	fprintf(fc_f, "\t");
	switch (fc_a->type)
	{
		case PLAIN:
			if (fc_a->co == RAINBOW)
				fprintf(fc_f, "[*]");
			else
				fprintf(fc_f, "[%ld]", (long) fc_a->co);
			break;
		case AHEAD:
			if (fc_a->co == RAINBOW)
				fprintf(fc_f, ">*>");
			else
				fprintf(fc_f, ">%ld>", (long) fc_a->co);
			break;
		case BEHIND:
			if (fc_a->co == RAINBOW)
				fprintf(fc_f, "<*<");
			else
				fprintf(fc_f, "<%ld<", (long) fc_a->co);
			break;
		case LACON:
			fprintf(fc_f, ":%ld:", (long) fc_a->co);
			break;
		case '^':
		case '$':
			fprintf(fc_f, "%c%d", fc_a->type, (int) fc_a->co);
			break;
		case EMPTY:
			break;
		case CANTMATCH:
			fprintf(fc_f, "X");
			break;
		default:
			fprintf(fc_f, "0x%x/0%lo", fc_a->type, (long) fc_a->co);
			break;
	}
	if (fc_a->from != fc_s)
		fprintf(fc_f, "?%d?", fc_a->from->no);
	for (fc_aa = fc_a->from->outs; fc_aa != NULL; fc_aa = fc_aa->outchain)
		if (fc_aa == fc_a)
			break;				/* 注意突破 */
	if (fc_aa == NULL)
		fprintf(fc_f, "?!?");		/* 缺失于输出链 */
	fprintf(fc_f, "->");
	if (fc_a->to == NULL)
	{
		fprintf(fc_f, "NULL");
		return;
	}
	fprintf(fc_f, "%d", fc_a->to->no);
	for (fc_aa = fc_a->to->ins; fc_aa != NULL; fc_aa = fc_aa->inchain)
		if (fc_aa == fc_a)
			break;				/* 注意突破 */
	if (fc_aa == NULL)
		fprintf(fc_f, "?!?");		/* 缺失于输入链 */
}
#endif							/* REG_DEBUG */

/*
 * dumpcnfa - 以人类可读的形式转储紧凑 NFA
 */
#ifdef REG_DEBUG
static void dumpcnfa(struct cnfa *cnfa,
		 FILE *fc_f)
{
	int			fc_st;

	fprintf(fc_f, "pre %d, post %d", cnfa->pre, cnfa->post);
	if (cnfa->bos[0] != COLORLESS)
		fprintf(fc_f, ", bos [%ld]", (long) cnfa->bos[0]);
	if (cnfa->bos[1] != COLORLESS)
		fprintf(fc_f, ", bol [%ld]", (long) cnfa->bos[1]);
	if (cnfa->eos[0] != COLORLESS)
		fprintf(fc_f, ", eos [%ld]", (long) cnfa->eos[0]);
	if (cnfa->eos[1] != COLORLESS)
		fprintf(fc_f, ", eol [%ld]", (long) cnfa->eos[1]);
	if (cnfa->flags & HASLACONS)
		fprintf(fc_f, ", haslacons");
	if (cnfa->flags & MATCHALL)
	{
		fprintf(fc_f, ", minmatchall %d", cnfa->minmatchall);
		if (cnfa->maxmatchall == DUPINF)
			fprintf(fc_f, ", maxmatchall inf");
		else
			fprintf(fc_f, ", maxmatchall %d", cnfa->maxmatchall);
	}
	fprintf(fc_f, "\n");
	for (fc_st = 0; fc_st < cnfa->nstates; fc_st++)
		dumpcstate(fc_st, cnfa, fc_f);
	fflush(fc_f);
}
#endif

#ifdef REG_DEBUG				/* dumpcnfa 的下属 */

/*
 * dumpcstate - 以人类可读的形式转储紧凑 NFA 状态
 */
static void dumpcstate(int fc_st,
		   struct cnfa *cnfa,
		   FILE *fc_f)
{
	struct carc *fc_ca;
	int			fc_pos;

	fprintf(fc_f, "%d%s", fc_st, (cnfa->stflags[fc_st] & CNFA_NOPROGRESS) ? ":" : ".");
	fc_pos = 1;
	for (fc_ca = cnfa->states[fc_st]; fc_ca->co != COLORLESS; fc_ca++)
	{
		if (fc_ca->co == RAINBOW)
			fprintf(fc_f, "\t[*]->%d", fc_ca->to);
		else if (fc_ca->co < cnfa->ncolors)
			fprintf(fc_f, "\t[%ld]->%d", (long) fc_ca->co, fc_ca->to);
		else
			fprintf(fc_f, "\t:%ld:->%d", (long) (fc_ca->co - cnfa->ncolors), fc_ca->to);
		if (fc_pos == 5)
		{
			fprintf(fc_f, "\n");
			fc_pos = 1;
		}
		else
			fc_pos++;
	}
	if (fc_ca == cnfa->states[fc_st] || fc_pos != 1)
		fprintf(fc_f, "\n");
	fflush(fc_f);
}

#endif							/* REG_DEBUG */
